favorite We need a little bit of your help to keep things running, click on this banner to learn more

ADA Classes - November 6

Minimal Spanning Tree

The connected graph is given. Find the spanning tree of minimal weight.


The first line contains two integers n and m (1n20000, 0m100000) - the number of vertices and number of edges in a graph. Each of the next m lines describes one edge. The edge number i is given with three integers bi, ei and wi (1bi, ein, 0wi100000) - the numbers of vertices and its weight.

Graph is connected.


Print one number - the weight of the minimal spanning tree.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
4 4
1 2 1
2 3 2
3 4 5
4 1 4
Output example #1