미적 감각

거북이 시럽은 $N$개의 장소가 $M$개의 도로로 연결된 마을에 산다. 장소는 $1, 2, \ldots, N$, 도로는 $1, 2, \ldots, M$으로 번호가 붙어 있다. $i$번 도로는 장소 $A_i$와 $B_i$를 직접 잇고, 길이는 $W_i$이며, 양방향으로 지날 수 있다. 모든 장소 쌍은 직접 또는 간접적으로 오갈 수 있고, 두 도로가 같은 두 끝점을 공유하는 경우는 없다.

각 도로에는 고유한 경관이 있고, 주민들은 도로마다 얼마나 아름다운지에 대해 의견이 일치한다. 도로 번호가 클수록 더 아름다워서, 1번 도로부터 $M$번 도로까지 아름다움이 점점 커진다.

주민들은 마을의 경관을 더 다듬고자 한다. 더 아름다운 도로의 똑같은 복제본을 그보다 아름다움이 엄격히 낮은 도로 위에 세운다. 도로 $j$를 도로 $i$에 복제할 수 있는 경우는 $i < j$일 때뿐이며, 이때 도로 $i$의 길이는 $W_i + W_j$가 된다. 주민들은 투표로 이 사업에 쓸 도로 쌍을 정확히 하나 고른다.

시럽은 집인 장소 $N$과 중앙광장인 장소 $1$ 사이를 자주 오간다. 사업이 끝난 뒤 장소 $1$과 $N$ 사이 최단 거리가 가질 수 있는 최댓값을 구한다.

첫째 줄에 $N$과 $M$이 주어진다. 이어지는 $M$개의 줄 가운데 $i$번째 줄에는 도로 $i$를 나타내는 $A_i$, $B_i$, $W_i$가 주어진다.

사업이 끝난 뒤 장소 $1$과 $N$ 사이 최단 거리의 최댓값을 한 줄에 정수 하나로 출력한다.

$3 \le N \le 300000$

$2 \le M \le 300000$

$1 \le A_i \ne B_i \le N$

$0 \le W_i \le 10^9$