Peanut is the mayor of a new city, Silvermill. Silvermill has N towns, numbered 0 to N-1, which are completely disconnected from one another. He hires a contractor, who gives him a list of E proposed roads, with the ith road proposed to connect towns Ai and Bi directly, at the cost of Ci dollars.
Peanut wishes to build a subset of roads proposed by the contractor, such that between any two towns, there exists a direct or indirect path between them. Help Peanut find the minimum possible cost of achieving this. It is guaranteed that there exists at least one subset of chosen roads that would accomplish this goal.
The first line of input will contain two integers, N and E.
The next E lines of input will contain three integers each, Ai, Bi and Ci.
The output should contain exactly one integer, the minimum cost, in terms of dollars, that Peanut needs to spend to connect the towns of Silvermill to one another.
1 ≤ N, E ≤ 106.
0 ≤ Ai, Bi < N.
1 ≤ Ci ≤ 109.
0 1 2
1 2 1
2 3 1
3 0 1
0 2 3
1 3 5