Module: Disjoint set system


Problem

8 /9


spanning tree

Problem

It is required to find a spanning tree of minimum weight in a connected graph.
 
Input
The first line of the input file contains two natural numbers n and m - the number of vertices and edges of the graph, respectively (1≤n≤20000, 0≤m≤100000). The next m lines contain the description of the edges, one per line. The edge number i is described by three natural numbers bi, ei and wi - the numbers of the ends of the edge and its weight, respectively (1≤bi,ei≤n, 0≤wi≤100000).
 
The graph is connected.
 
Output
Print a single integer - the weight of the minimum spanning tree.
 
Input Output
4 4
1 2 1
2 3 2
3 4 5
4 1 4
7