Highways and King

There are $n$ towns conveniently labeled with $1,2,...,n$ in Flatland Kingdom and $m$ bidirectional highways are allowed to be built.

The $i$-th highway can be built between cities $a_i$ and $b_i$ with cost $c_i$.

The Flatland Road Company plans to build the ($n-1$) allowed highways with the least total cost to connect any of two cities directly or indirectly.

The King of Flatland is going to remove some of the highways from the list of the allowed highways. He would like to know the minimum number of highways to be removed to strictly increase the total cost.

Note that the total cost is considered as $+\infty$ if no valid ($n-1$) highways exist after removing. It is also counted as «total cost strictly increases».

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(2\le n\le 50)$ and $m(n-1\le m\le n^2)$. The $i$-th of the following $m$ lines contains $a_i,b_i,c_i(1\le a_i,b_i\le n,1\le c_i\le 10^9)$.

• Any two cities will be connected if all $m$ allowed highways are built.

• The sum of $n$ does not exceed $10^3$.

Output

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

Examples