22165_Second-bestminimumspanningtree

Given a connected undirected graph with n vertexes and m edges with weights, I think it is easy for you to compute the minimum spanning tree. But what about the Second-best minimum spanning tree?

In this problem, n is no more than m. And you can assume that all edge weights are distinct.

The Second-best minimum spanning tree is defined as follows: let T denotes the set of all the spanning tree of G, T' denotes the minimum spanning tree of G, then T'' is the second-best minimum spanning tree of G such that weight(T'') = min{ weight( T''' ) | T''' ∈T - T' }.

For each test case, the first line contains two integer n, m ( 0 < n ≤ 100000, n ≤ m ≤ 1000000 ).

Then there are m lines, each contains three integer x, y, w. It means that there is an edge between vertex x and vertex y with weight w ( 1 ≤ x, y ≤ n, 1 ≤ w ≤ 1000000 ). The test data ensure that the second-best minimum spanning tree do exist.

For each test case, print the weight of the second-best minimum spanning tree in a single line.

3 3
1 2 1
1 3 2
2 3 3
4 5
1 2 1
2 3 2
3 4 3
1 4 4
2 4 5

4
7