暂无测试数据。

Description

给你一个无向连通图（无自环无重边），你每次可以选择其中的一条边，将这条边的权值 $+1$，问你要使这个图的最小生成树的方案唯一，所需要进行的最少操作数。

Input

输入包含多组测试数据，第一行一个整数 $T$，表示测试数据组数。每组测试数据包括以下内容。
第一行两个整数 $n$ 和 $m$，分别表示顶点数和边数。
接下来 $m$ 行，每行三个整数 $x$、 $y$ 和 $w$，表示顶点 $x$ 和 $y$ 间有一条权值为 $w$ 的
边相连。对于任意两个顶点，最多只有一条边相连。

Output

对于每组测试数据输出一行包含一个整数，表示需要的最少操作次数。

Sample

Sample input

2
8 10
1 2 1
2 3 2
2 4 5
1 4 2
6 3 3
6 1 3
3 5 2
3 7 1
4 8 1
6 2 4
3 3
1 2 1
2 3 2
1 3 3

Sample Output

1
0

Hint

对于所有数据：$T\leq 10$，$n\leq 1000$，$m\leq 5e6$。