Very Important Edge

Interview

Time limit3sMemory limit2048 MB

Summary

Given a weighted connected graph, find the edge whose removal gives the largest minimum spanning tree weight, and print that weight.

Level: Medium6 of 10
Topics: Minimum spanning tree, Graph, Union-find
Solved: No attempts yet

Problem

You are given a simple connected graph where each edge has a non-negative weight. A minimum spanning tree is a connected, acyclic subset of the edges with the smallest total weight. Find the edge whose deletion maximizes the weight of the minimum spanning tree of the graph. The graph is guaranteed to stay connected after deleting any single edge.

Input

The first line contains two integers $n$ ( $3 \le n \le 10^5$ ) and $m$ ( $3 \le m \le 10^6$ ), the number of vertices and the number of edges. The vertices are numbered from $1$ to $n$ . Each of the next $m$ lines contains three integers $a$ , $b$ , and $w$ ( $1 \le a < b \le n$ , $1 \le w \le 10^6$ ), describing an edge between vertices $a$ and $b$ with weight $w$ .

Output

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

Examples3

Example 1
Input
```
3 3
1 2 1
2 3 2
1 3 2
```
Expected output
```
4
```
Example 2
Input
```
4 5
2 3 5
1 2 2
1 3 4
1 4 2
3 4 3
```
Expected output
```
10
```

Example 3

Input

Expected output