1090. Second Best Minimum Spanning Tree

Given a connected undirected weighted graph with n nodes and edges [u, v, w], return the total weight of the second-best minimum spanning tree — the smallest spanning-tree weight strictly using a different set of edges from some MST. Return -1 if no second spanning tree exists (or the graph is not connected). The input is JSON {n, edges}.

Input: JSON {n, edges} with edges [u, v, w].

Output: Integer — the second-best MST weight, or -1.

Examples

Input: {"n":4,"edges":[[0,1,1],[1,2,2],[2,3,3],[0,3,4],[0,2,5]]}
Output: 7
Explanation: MST is 6; swapping one edge gives 7.

Input: {"n":3,"edges":[[0,1,1],[1,2,2],[0,2,3]]}
Output: 4
Explanation: Second-best triangle tree.

Input: {"n":2,"edges":[[0,1,5]]}
Output: -1
Explanation: Only one spanning tree.

Constraints

• 2<=n<=1000
• connected

Asked by