8495: Assassination

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 nnodes and m wires (wires are bi-directional) on the circuit board. Each wire connects two nodes, and ith 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?

First line has one integer T, indicating there are Ttest 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≤n,wi≤105,n−1≤m≤min(2n(n−1),2×105),∑m≤106

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