Minimum Spanning Tree?

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

     Given a connected, undirected graph, a spanning tree of that graph is a sub graph that is a tree and connects all the vertexes together. A single graph can have many different spanning trees. We can also assign a weight to each edge, which is a number representing how unfavorable it is, and use this to assign a weight to a spanning tree by computing the sum of the weights of the edges in that spanning tree. A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree.
    As we know, a single graph can also have many different minimum spanning trees. Given a connected, undirected,weighted graph with N vertexes and M edges, we wants to know how many edges can appear in the minimum spanning trees of the graph.
    For example, the sample input bellow is:
                      

Input

   There are multiple test cases.
    For each test case:
   
The fist line is two integers N and M (1 <= N <= 100000N-1<= M <= 500000).
   
Each of the following M lines contains three integers UV and W (1<= U,V<= N, 0<= W <= 1000) .It shows that the weight of undirected edge(U , V) is W.

Output

    For each test case, output a single integer in one line representing the number of different edges appeared in the minimum spanning trees of the given graph.

Sample Input

4 5
1 2 20
1 3 10
2 3 2
2 4 2
3 4 1

Sample Output

4

Hint

 

Source

qinchuan