The Runner-Up Spanning Tree
Print the weight of the second-best (next cheapest) spanning tree — the minimum weight over all spanning trees that differ from at least one minimum spanning tree in at least one edge. Print −1 if fewer than two spanning trees exist.
Input: the first line has N and M; each of the next M lines has u v w.
Output: the second-best spanning-tree weight, or −1.
Constraints:
- 2 ≤ N ≤ 200
- N−1 ≤ M ≤ 600
- 1 ≤ w ≤ 1000
Sample Tests
Input 1
3 3 1 2 1 2 3 2 1 3 2
Output 1
3
Input 2
2 1 1 2 5
Output 2
-1
Discussion (opens after you solve — no spoilers before)
No comments yet.