Very Important Edge

시간 제한3초메모리 제한2048 MB

요약

가중치가 있는 단순 연결 그래프에서 간선 하나를 지웠을 때 최소 신장 트리 무게가 가장 커지도록 하는 간선을 골라, 그 무게를 출력한다.

난이도: 어려움10점 중 8점
유형: 최소 신장 트리, 그래프, 유니온 파인드, 정렬
정답자: 아직 제출이 없습니다

문제

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.

입력

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\le10^6$ ). This denotes an edge between vertices $a$ and $b$ with weight $w$ .

출력

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

예제3

예제 1
입력
```
3 3
1 2 1
2 3 2
1 3 2
```
예상 출력
```
4
```
예제 2
입력
```
4 5
2 3 5
1 2 2
1 3 4
1 4 2
3 4 3
```
예상 출력
```
10
```

예제 3

입력

예상 출력