두 경로

노드가 $n$개(번호는 $1$부터 $n$까지)이고 간선이 $m$개인 무방향 그래프가 주어진다. 각 간선에는 길이가 있다. 그래프에는 중복 간선과 자기 자신으로 향하는 간선이 없다.

Alice와 Bob은 게임을 하려고 한다. 두 사람은 각각 $1$에서 $n$으로 가는 경로를 하나씩 골라야 한다(단순 경로일 필요는 없다). 두 경로는 서로 달라야 한다.

Alice가 먼저 움직이며, $1$에서 $n$으로 가는 최단 경로 중 하나를 골랐다. 이제 Bob의 차례이다. Bob은 Alice의 경로와 다른 $1$에서 $n$으로 가는 경로 중 가장 짧은 것을 고르려고 한다. 그 경로의 길이를 구하시오.

두 경로 $S$와 $T$는 간선의 개수가 다르거나, $S$의 $i$번째 간선과 $T$의 $i$번째 간선이 다른 정수 $i$가 존재할 때에만 서로 다르다고 본다.

첫째 줄에 노드의 개수 $n$과 간선의 개수 $m$이 주어진다 ($2 \le n \le 10^5$, $1 \le m \le 10^5$). 다음 $m$개의 줄에는 정수 $a$, $b$, $w$가 주어지는데, 이는 노드 $a$와 노드 $b$ 사이에 길이가 $w$인 간선이 있음을 뜻한다 ($1 \le a, b \le n$, $1 \le w \le 10^9$). $1$에서 $n$으로 가는 경로가 적어도 하나 존재함이 보장된다.

Bob이 고를 수 있는 유효한 최단 경로의 길이를 한 줄에 정수로 출력한다.