暂无测试数据。

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\)。