e-olymp
Competitions

Spanning Tree + DSU

Minimum spanning tree

Find the weight of minimum spanning tree for a weighted undirected connected graph.

Input

The first line contains the numbers n and m (1n100, 1m6000), where n is the number of vertices in the graph and m is the number of edges. In each of the next m lines the triple of numbers a, b, c are written, where a and b are the numbers of vertices connected by an edge and c is the weight of edge (a positive number not exceeding 30000).

Output

Print the weight of minimum spanning tree.

Time limit 1 second
Memory limit 64 MiB
Input example #1
3 3
1 2 1
2 3 2
3 1 3
Output example #1
3