버그

전자 달력에 버그가 생겼습니다. 프로그래머들이 흔히 버그라 부르는 종류의 결함입니다. 이 버그 때문에 짝수 정수는 달력에 입력할 수 없습니다.

당신은 바이트타운(Bytetown)에서 비트시티(Bitcity)로 출장을 갈 계획입니다. 당연히 가장 짧은 경로로 이동하고 싶습니다. 출장을 마치고 돌아오면 이동한 경로의 길이를 달력에 기록해야 하는데, 버그 때문에 그 길이는 반드시 홀수여야 합니다.

바이트랜드(Byteland)의 도로망은 앞으로도 여러 번 개편될 것이고 버그도 한동안 고쳐지지 않을 것이므로, 비슷한 문제를 언제든 풀 수 있도록 프로그램을 작성하기로 했습니다.

다음을 수행하는 프로그램을 작성하세요.

• 표준 입력에서 바이트랜드 지도 정보를 읽는다.
• 바이트타운에서 비트시티까지 가는, 길이가 홀수인 가장 짧은 경로의 길이를 구하거나 그런 경로가 없음을 판별한다.
• 결과를 표준 출력에 쓴다.

첫째 줄에 도시의 수 $n$과 도로의 수 $m$이 공백 하나로 구분되어 주어집니다 ($2 \le n \le 200\,000$, $0 \le m \le 500\,000$). 도시는 $1$번부터 $n$번까지 번호가 매겨져 있으며, 바이트타운은 $1$번, 비트시티는 $n$번입니다.

이어지는 $m$개의 줄에 도로 정보가 주어집니다. 각 줄에는 세 정수 $a$, $b$, $c$가 공백으로 구분되어 주어지며 ($1 \le a, b \le n$, $a \ne b$, $1 \le c \le 1\,000$), 이는 도시 $a$와 도시 $b$를 잇는 길이 $c$의 양방향 도로를 나타냅니다.

바이트타운에서 비트시티까지 가는, 길이가 홀수인 가장 짧은 경로의 길이를 정수 하나로 출력합니다. 경로는 같은 도시나 도로를 여러 번 지날 수 있습니다. 진행 방향을 바꾸는 것(되돌아가는 것 포함)은 도시에서만 할 수 있습니다. 그런 경로가 존재하지 않으면 $0$을 출력합니다.