安培（符号：A）是电流的国际单位制基本单位。在电路板上，有一种名为 Ambere 的电流。他与任何其他电流都不同，因为他经过的导线永远不会构成回路（他可以走回头路，但他访问过的所有导线不会形成环）。

电路板上有 $n$ 个节点和 $m$ 条导线（导线是双向的）。每条导线连接两个节点，第 $i$ 条导线有 $w_i$ 个元件。如果电流通过某条导线，该导线上的元件就能工作。

Ambere 可以从任意节点出发，并在任意节点停止。Ambere 访问过一次或多次的导线上的元件都能工作。Ambere 是一位心地善良的电流，所以他会尽可能多地经过元件。

但你不是个好人。作为国际电工委员会（IEC）的一员，你对电流永远无法构成回路感到非常愤怒。因此，你计划向导线派遣几名杀手。如果 Ambere 经过一条有杀手的导线，他就会被暗杀。

你的委员会提供的资金有限，所以你想知道你最少需要多少名杀手？

输入格式

第一行包含一个整数 $T$，表示有 $T$ 组测试数据。每组数据中：

第一行包含两个整数 $n, m$，表示节点数和导线数。

接下来的 $m$ 行，每行包含 3 个整数 $u, v, w$，表示一条连接节点 $u$ 和节点 $v$ 的导线，且该导线上有 $w$ 个元件。

保证图是连通的，且不包含自环或重边，具有相同 $w$ 的导线数量不超过 $10^2$。

$1 \le n, w_i \le 10^5, n - 1 \le m \le \min\left(\frac{n(n-1)}{2}, 2 \times 10^5\right), \sum m \le 10^6$

输出格式

对于每组数据，输出一个整数，表示答案。

样例

输入格式 1

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

输出格式 1

1
3