In ICPCCamp, there are n towns conveniently labeled with and m bidirectional roads planned to be built.
The i-th road will be built between cities and with cost .
The builders in ICPCCamp will build the (n - 1) roads with the least total cost to connect any of two cities directly or indirectly.
Bobo, the mayor of ICPCCamp is going to remove some of the roads from the construction plan.
He would like to know the minimum number of roads to be removed to *strictly increase* the total cost.
Note that the total cost is considered as if no valid (n - 1) roads exist after removing. It is also counted as "total cost strictly increases".

The input contains zero or more test cases and is terminated by end-of-file. For each test case:

The first line contains two integers n and m.
The i-th of the following m lines contains .

* 
* 
* 
* 
* Any two cities will be connected if all m roads are built.
* The sum of n does not exceed .

For each case, output an integer which denotes the result.

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

1
1
2
3