여행세

바이트 왕국의 통치자는 전 세계적인 흐름에 발맞추어 가능한 모든 것에 세금을 매기기로 했다. 가장 최근에 도입된 세금은 이른바 여행세로, 나라 안을 이동하는 모든 사람이 내야 한다.

바이트 왕국의 모든 도로에는 세율이 정해져 있다. 여행 중 어떤 도시를 지날 때에는 그 도시의 관청에서 세금을 내야 하는데, 이 세금은 그 도시로 들어올 때 이용한 도로의 세율과 그 도시에서 나갈 때 이용하는 도로의 세율 중 더 큰 값으로 정해진다. 출발 도시와 도착 도시에서도 세금을 내며, 이때는 이용하는 도로가 하나뿐이므로 그 한 도로의 세율만으로 세금을 계산한다.

당신의 친구 바이타자르는 $1$번 도시에서 $n$번 도시까지 여행하려고 한다. 그가 내는 세금의 총합이 최소가 되도록 이동 경로를 계획해 주어라.

첫째 줄에 도시의 수 $n$과 도로의 수 $m$이 주어진다 ($2 \le n \le 100\,000$, $1 \le m \le 200\,000$). 도시에는 $1$번부터 $n$번까지 번호가 붙어 있다.

이어지는 $m$개의 줄에는 각 도로의 정보가 주어진다. $i$번째 줄에는 세 정수 $a_i$, $b_i$, $c_i$가 주어진다 ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le c_i \le 1\,000\,000$). 이는 도시 $a_i$와 $b_i$가 양방향 도로로 연결되어 있고 그 도로의 세율이 $c_i$바이트탈러임을 뜻한다. 임의의 두 도시 사이에는 도로가 최대 한 개 있다.

$1$번 도시에서 $n$번 도시까지 이동하는 데 드는 세금의 최솟값(바이트탈러 단위)을 정수 하나로 한 줄에 출력한다. 두 도시를 잇는 도로의 경로는 항상 존재한다고 가정해도 된다.

예를 들어 도로가 $\{1,2\}$ 세율 $5$, $\{1,3\}$ 세율 $2$, $\{2,3\}$ 세율 $1$, $\{2,4\}$ 세율 $4$, $\{3,4\}$ 세율 $8$로 주어졌다고 하자. 최적 경로는 도시 $1 \to 3 \to 2 \to 4$를 지난다. 각 도시에서 내는 세금은 차례대로 $2$, $\max(2, 1) = 2$, $\max(1, 4) = 4$, $4$이고, 이를 모두 더하면 $12$가 된다.