Second MST Weight

Problem

Find the weight of the lightest spanning tree strictly heavier than the MST.

All edge weights are distinct and edges is an undirected [u, v, w] list. Compute the MST, then for each tree edge rerun Kruskal with that edge banned and keep the smallest resulting spanning weight above the MST. Return -1 when the graph is disconnected, has a single node, or admits only one spanning tree.

Hint

Banning one MST edge at a time is enough because every non-MST spanning tree differs from the MST somewhere.

Test cases

case 1

in: [4,[[0,1,1],[1,2,2],[2,3,3],[3,0,4],[0,2,5]]]

expected: 7

case 2

in: [3,[[0,1,1],[1,2,2]]]

expected: -1

case 3

in: [3,[[0,1,1],[1,2,2],[0,2,3]]]

expected: 4

case 4

in: [1,[]]

expected: -1

case 5

in: [3,[[0,1,1]]]

expected: -1

Starter codePython

def second_mst_weight(n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor