The Sponsor's Cable

Difficulty: 2000 4000 ms 128 MB

graphs greedy union-find

A sponsor insists that edge number K be part of the network. Print the minimum total cost of a spanning tree CONTAINING edge K, or IMPOSSIBLE.

Input: the first line has N, M and K; each of the next M lines has u v w (edges numbered 1..M in input order).

Output: the minimum spanning-tree weight that includes edge K, or IMPOSSIBLE.

Constraints:

• 2 ≤ N ≤ 10⁴
• 1 ≤ M ≤ 2×10⁴

Sample Tests

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

7

2 1 1
1 2 3

3

Read the Editorial