Problem K
Very Important Edge

You are given a simple connected graph where each edge is assigned a non-negative weight. Recall that a minimum spanning tree of a graph is a connected, acyclic subset of the edges of the graph with minimum total weight. Find an edge which maximizes the minimum spanning tree weight of a given graph if that edge is deleted. It is guaranteed that the input graph remains connected after deleting any one edge.

Input

The first line of input contains two integers $n$ ($3 \le n \le 10^5$) and $m$ ($3 \le m \le 10^6$), where $n$ is the number of vertices and $m$ is the number of edges in the input graph. The vertices are numbered from $1$ to $n$.

Each of the next $m$ lines contains three integers $a$, $b$ ($1\le a<b\le n$) and $w$ ($1\le w\le 10^6$). This denotes an edge between vertices $a$ and $b$ with weight $w$.

Output

Output a single integer, which is the minimum spanning tree weight of the input graph after the right edge is deleted.

3 3
1 2 1
2 3 2
1 3 2

4

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

10

5 7
2 5 8
1 3 19
4 5 9
1 5 15
1 2 14
3 4 16
2 4 15

54