해양 탐사

해양 탐험가 카렌은 N개의 섬으로 이루어진 군도를 탐험하고 있다. 섬들 사이에는 M개의 해로가 있으며, 각 해로는 두 섬을 연결하고 거리가 주어진다.

본섬(0번 섬)에서 출발하여 가장 멀리 있는 섬까지의 최단 거리를 구하여라.

입력

첫째 줄에 섬의 수 N과 해로의 수 M이 주어진다. 다음 M줄에 걸쳐 해로의 양 끝 섬 번호 U, V와 거리 W가 주어진다.

출력

본섬(0번)에서 가장 멀리 있는 섬까지의 최단 거리를 출력한다.

제한

• 2 ≤ N ≤ 100000
• 1 ≤ M ≤ 200000
• 0 ≤ U, V < N, U ≠ V
• 1 ≤ W ≤ 100000
• 모든 섬은 본섬에서 도달 가능하다

예제 입력 1

4 4
0 1 2
1 2 3
2 3 1
0 3 10

예제 출력 1

6

예제 입력 2

3 2
0 1 5
1 2 3

예제 출력 2

8

설명: 예제 1에서 0→1→2→3 경로의 거리는 2+3+1=6이고, 0→3 직접 거리는 10이므로 가장 먼 섬(3번)까지의 최단 거리는 6이다.