미니언들의 놀이

시간 제한2초메모리 제한1024 MB

요약

가중치가 있는 무방향 다중 그래프에서 간선을 한 번씩만 지나는 순환 경로 중, 경로의 최소 간선 가중치와 최대 간선 가중치의 합이 가장 큰 값을 구합니다.

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

문제

그루는 소녀들과 쇼핑을 떠났고, 할 일이 없어진 미니언들은 지루해졌다. 미니언들은 모두가 참가하는 경쟁을 열어 시간을 보내기로 했다.

그루 연구소의 지도에는 $n$ 개의 체크포인트가 표시되어 있다. 체크포인트 사이에는 양방향 통로가 $m$ 개 있고, 통로마다 바나나가 여러 개 놓여 있다. 미니언은 임의의 체크포인트에서 출발해 통로를 따라 달리는데, 각 통로는 최대 한 번만 지날 수 있다. 달린 뒤에는 출발한 체크포인트로 돌아온다. 미니언이 이렇게 순환 경로를 달려 바나나가 $c_1, c_2, \ldots, c_k$ 개 놓인 통로들을 지났다면, 이 경로의 점수는 $\min(c_1, c_2, \ldots, c_k) + \max(c_1, c_2, \ldots, c_k)$ 이다.

미니언 데이브는 이 경쟁에서 꼭 이기고 싶어 한다. 점수가 가장 높은 순환 경로를 찾아 데이브를 도와주자.

입력

첫 줄에 두 정수 $n$ , $m$ ( $1 \le n, m \le 100\,000$ )이 주어진다. 각각 체크포인트의 수와 통로의 수이다. 이어지는 $m$ 개의 줄에는 세 정수 $v$ , $u$ , $w$ ( $1 \le v, u \le n$ ; $v \ne u$ ; $0 \le w \le 10^9$ )가 한 줄씩 주어진다. 이는 $v$ 번 체크포인트와 $u$ 번 체크포인트를 잇는 통로, 그리고 그 통로에 놓인 바나나의 수 $w$ 이다. 같은 두 체크포인트를 잇는 통로가 여러 개 있을 수 있다.

출력

모든 순환 경로에 대해 바나나 수의 최솟값과 최댓값을 더한 값 중 가장 큰 값을 한 줄에 출력한다. 순환 경로가 하나도 없으면 0을 출력한다.

힌트

첫 번째 예시에는 순환 경로가 하나뿐이므로, 그 경로의 바나나 최솟값과 최댓값을 더한 $1+1=2$ 가 답이다. 두 번째 예시도 순환 경로가 하나뿐이며, 답은 $1+2=3$ 이다. 세 번째 예시에는 순환 경로가 세 개 있다. 1-2-3-1은 $1+2=3$ 점, 1-2-4-1은 $2+2=4$ 점, 1-4-2-3-1은 $1+2=3$ 점을 얻는다. 따라서 두 번째 경로로 달리는 것이 가장 좋고, 답은 4이다. 네 번째 예시에는 순환 경로가 없으므로 답은 0이다.

예제4

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