408978: GYM103401 G Environmental friendly

In response to the national call for energy conservation and emission reduction, Master Yi, the director of the Transportation Bureau in Pigeon province, decided to demolish some unnecessary roads to reduce waste of resources. There are $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$ in his province. Also there are $$$m$$$ roads connecting the cities. One can go from city $$$u_i$$$ to $$$v_i$$$ (and vise versa) using $$$i$$$-th road, the length of this road is $$$w_i$$$.

Master Yi doesn't want to waste the money of the province, so he is going to close some of the roads in response to the country's call to save resources. Please tell Master Yi the maximum number of the roads which can be closed such that the distance between any two cities in Pigeon province does not change.

The first line contains an single integer $$$T\ (1\le T\le 10)$$$, which is the number of the text cases.

Then T cases follow, each case starts with two integers $$$n,\ m\ (2\le n\le 200, 1\le m\le 100,000)$$$.

Each of the next $$$m$$$ lines contains three integers $$$u_i,\ v_i,\ w_i\ (1\le u_i,\ v_i\le n;\ u_i\neq v_i;\ 1\le w_i\le 1,000,000,000)$$$. Note that there may be more than one roads between two cities.

For each case, output a single integer representing the maximum number of the roads which can be closed.

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

2
1