Prim Algorithm — Minimum Spanning Tree

Practice this coding question on Coding Gurukul.

Problem statement

Given an undirected weighted graph, find the total weight of a minimum spanning tree using Prim’s algorithm. Start at vertex 0. Use a min-priority queue to repeatedly add the cheapest edge to a vertex not yet in the tree. If the graph is disconnected, print IMPOSSIBLE. A single vertex has answer 0. Negative weights, repeated edges and self-loops are allowed; do not include self-loops in the tree. Print only the total weight, using signed 64-bit arithmetic. Target O((n+m) log n) time. Worked example The edges 0–1, 1–2 and 2–3 have weights 1, 2 and 3. They connect all four vertices with minimum total weight 6.

Input format

First line: n m. Next m lines: undirected edge u v w.

Output format

Print the minimum total cost, or IMPOSSIBLE.

Constraints

1 <= n <= 100000; 0 <= m <= 200000; 0 <= u,v < n; -10^9 <= w <= 10^9.

Sample input

4 5
0 1 1
1 2 2
2 3 3
0 3 10
0 2 8

Sample output

6

Sign in to run or submit a solution in C++, Java or Python.