The problem wants us to find the second-smallest spanning tree. To do so, we can first generate the minimum spanning tree (MST), keeping track of which edges were not used. We can then iterate over these unused edges, and use the cycle property of a minimum spanning tree: if there is a cycle, the heaviest edge will not be in the minimum spanning tree. To find the edge with the largest weight, we can use either HLD or a sparse table to query for the LCA is ~\mathcal O(\log N)~ time, and find the maximum edge from either endpoint of the edge in ~\mathcal O(\log N)~. We store the weight of this edge subtracted from the weight of the original MST if it is less than the weight of the edge currently in consideration, and print the minimum of these weights. Note that you should print -1 if there are less than ~N - 1~ edges in the original MST, or if you cannot remove any of the edges in the original MST using the cycle theorem.

Complexity: ~\mathcal O(M (\log N + \log M))~