An MST Problem

View as PDF

Submit solution

Points: 10
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

Given N nodes and M weighed bidirectional edges, build the Minimum Spanning Tree of the graph.

Input Specification

The first line will contain two integers N, M\ (1 \le N \le 1\ 000, 1 \le M \le 10^5).

The next M lines will each contain three integers, u_i, v_i, w_i\ (1 \le u_i, v_i \le N, 1 \le w_i \le 10^9).

Output Specification

Print the sum of the edges in the minimum spanning tree on the first line. If no minimum spanning tree can be built using the M edges, print 0.

Sample Input

4 7
1 2 1
1 3 1
1 4 5
1 2 10
1 1 3
3 4 2
2 4 7

Sample Output

4

Comments

There are no comments at the moment.