树是一个无环的连通无向图。边仙人掌是一种无向连通图,没有环和平行边,每条边最多属于一个环。
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