Source: Super League of Chinese College Students Algorithm Design 2022, Contest 2 by HDU.

Problem Description

Ampere (symbol: A), is the SI base unit of electric current. On a circuit board, there is a electric current called Ambere. He is different from any other currents because the wires he passed never complete the circuit (he can go back, but all wires he visited won't form the loop).

There are $n$ nodes and $m$ wires (wires are bi-directional) on the circuit board. Each wire connects two nodes, and $i$'th wire has $w_i$ components. If a current passes a wire, the components on the wire would be able to work.

Ambere can start from any node, and stop at any node. Components on wires which Ambere visited once or more will be able to work. Ambere is a good-hearted current so he will pass as much components as he can.

But you're not a nice guy. As a member of IEC(International Electro technical Commission), you feel extremely angry that a current never complete the circuit. So you plan to send several killers to wires. If Ambere passes a wire with a killer, he would be assassinated.

Your commission offers limited funds, so you want to know what's the minimal number of killers you need in order to assassinate Ambere?

Input

First line has one integer $T$, indicating there are $T$ test cases. In each case:

First line has two integers $n, m$, indicating the number of nodes and the number of wires.

For next $m$ lines, each line has $3$ integers $u, v, w$, indicating a wire connecting node $u$ and node $v$, and there're $w$ components on the wire.

It is guaranteed that the graph is connected and doesn't contain loops or multiple edges, the number of wires with a same $w$ would be no more than $10^2$ .

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

Output

In each case, print one integer, indicates the answer.

Sample

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
3