Kruskal Algorithm
easy
There are n vertices and there are edges in between some of the vertices. Find the sum of edge weight of minimum spanning tree.
Constraints
1<= n <= 1000 1<= e <= n*(n-1)/2
Format
Input
First line contains number of vertices. Second line contains number of edges. Each of next E lines contain 3 number u and v and c denoting an edge between u and v with weight c.
Output
print the sum of edge weight of MST.
Example
Sample Input
7
8
0 1 10
1 2 10
2 3 10
0 3 40
3 4 2
4 5 3
5 6 3
4 6 8
Sample Output
38