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 |