Given ~N~ nodes and ~M~ weighed bidirectional edges, build the Minimum Spanning Tree of the graph.

Input Specification

The first line will contain two integers ~N, M~ ~(1 \le N \le 1~ ~000, 1 \le M \le 10^5)~.

The next ~M~ lines will each contain three integers, ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le N, 1 \le w_i \le 10^9)~.

Output Specification

Print the sum of the edges in the minimum spanning tree on the first line. If no minimum spanning tree can be built using the ~M~ edges, print 0.

Sample Input

4 7
1 2 1
1 3 1
1 4 5
1 2 10
1 1 3
3 4 2
2 4 7

Sample Output

4