The President of Berland turned to you for help! There are n cities in his country. There are two-way roads between some pairs of cities. The tourist season will open very soon, but the roads of Berland are not at all ready for such a test.
The President wants to repair a set of roads so that the total cost of repairs is minimal and one can get from any city in Berland to any other using only the repaired roads.
Find a lot of roads that need to be repaired, your friend will help you. You only need to calculate the minimum repair cost.
It is guaranteed that there is always a required set of roads.
Input:
The first line contains two integers - n and m (2 <= n <= 300000, n - 1 <= m <= 300000).
The next m lines contain three numbers - u, v and w (1 <= u, v <= n, 0 <= w <= 109) - the road between cities u and v whose repair cost is w.