매우 중요한 간선

면접 대비

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

요약

가중치가 있는 연결 그래프에서 간선 하나를 제거했을 때 최소 신장 트리의 가중치 합이 가장 커지는 간선을 찾고, 그 값을 출력합니다.

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

문제

간선마다 음이 아닌 가중치가 할당된 단순 연결 그래프가 주어진다. 최소 신장 트리는 간선들의 부분집합 가운데 연결되어 있고 사이클이 없으며 총 가중치가 가장 작은 것이다. 간선 하나를 삭제했을 때 그래프의 최소 신장 트리 가중치가 최대가 되도록 하는 간선을 찾아라. 입력 그래프는 어떤 간선을 하나 삭제하더라도 연결 상태를 유지한다고 보장된다.

입력

첫째 줄에 정점의 개수 $n$ ( $3 \le n \le 10^5$ )과 간선의 개수 $m$ ( $3 \le m \le 10^6$ )이 주어진다. 정점은 1번부터 $n$ 번까지 번호가 매겨져 있다. 다음 $m$ 개 줄에는 각각 세 정수 $a$ , $b$ , $w$ ( $1 \le a < b \le n$ , $1 \le w \le 10^6$ )가 주어지며, 이는 정점 $a$ 와 $b$ 를 잇는 가중치 $w$ 의 간선을 뜻한다.

출력

간선을 올바르게 삭제한 뒤 그래프의 최소 신장 트리 가중치를 정수 하나로 출력한다.

예제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

입력

예상 출력