← 返回题目列表

Codeforces · 720/B

B. 仙人掌恐惧症

中文机器翻译题面 查看原题

树是一个无环的连通无向图。边仙人掌是一种无向连通图,没有环和平行边,每条边最多属于一个环。

Vasya 有一个边缘仙人掌,该图的每个边缘都有一些颜色。

Vasya 希望删除最少数量的边缘,使他的仙人掌变成一棵树。 Vasya 希望以这样的方式制作它,即生成的树中有尽可能多的不同颜色的边缘。帮助他找出最终的树有多少种不同的颜色。

输入

第一行包含两个整数:n, m (2 ≤ n ≤ 10 000) - 分别是 Vasya 图中的顶点数和边数。

以下 m 行每行包含三个整数:u, v, c (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ c ≤ m) - 由相应边连接的顶点数及其颜色。保证所描述的图确实是边缘仙人掌。

输出

输出一个整数:生成的树可以具有的不同颜色的最大数量。

示例

输入 #1

4 4
1 2 4
2 3 1
3 4 2
4 2 3

输出 #1

3

输入 #2

7 9
1 2 1
2 3 4
3 1 5
1 4 5
4 5 2
5 1 6
1 6 4
6 7 6
7 1 3

输出 #2

6