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.