Second-best spanning tree

Write codeHard40 min

Your task

Given n nodes and a list of weighted undirected edges [u, v, w], return the total weight of the second-best (strictly second smallest) spanning tree: the minimum weight achievable by any spanning tree whose total weight is strictly greater than the MST weight. If every spanning tree has the same weight as the MST (or the graph is disconnected / has only one spanning tree), return -1. Edge weights are positive integers.

Examples

second_best_mst(n: int, edges: list[list[int]]) -> int

Example 1

Inputsecond_best_mst(4, [[0, 1, 1], [1, 2, 1], [2, 3, 1], [0, 3, 2], [0, 2, 2]])

Output4