Second Smallest Spanning Tree

Given an undirected graph G, find the weight of a spanning tree whose total weight is greater than the minimum spanning tree and is as small as possible among such trees. This tree is called the second smallest spanning tree.

The figure shows an example of a minimum spanning tree and a second smallest spanning tree.

The first line contains the number of vertices V (1 <= V <= 50,000) and the number of edges E (1 <= E <= 200,000). Each of the next E lines contains two vertices joined by an edge and the weight of that edge. Each weight is an integer from 0 to 100,000. The answer does not exceed (2^{31}-1).

Vertices are numbered from 1 to V.

Print the total weight of the second smallest spanning tree. If no spanning tree exists, or if no spanning tree has total weight strictly greater than the minimum spanning tree, print -1.