Cheapest Network

Difficulty: 1500 4000 ms 128 MB

graphs greedy union-find

Print the minimum total cost to keep all N nodes connected using a subset of the offered edges, or IMPOSSIBLE.

Input: the first line has N and M; each of the next M lines has u v w.

Output: the MST weight, or IMPOSSIBLE.

Constraints:

• 1 ≤ N ≤ 10⁴
• 0 ≤ M ≤ 2×10⁴
• 1 ≤ w ≤ 10⁹

Sample Tests

4 5
1 2 1
2 3 2
3 4 1
1 4 5
1 3 2

4

2 0

IMPOSSIBLE

Read the Editorial