Bug

Your electronic calendar has a bug, the kind of defect programmers know well. Because of this bug, even integers cannot be entered into the calendar.

You are planning a business trip from Bytetown to Bitcity. Naturally, you want to travel along the shortest possible route. After you return, you must record the length of that route in the calendar, so the length has to be an odd integer.

Because the road network of Byteland will probably be rebuilt many times and the bug will not be fixed for a long while, you decide to write a program that can solve this kind of problem whenever it comes up.

Write a program that:

• reads a description of the map of Byteland from standard input,
• computes the length of the shortest odd-length route from Bytetown to Bitcity, or determines that no such route exists,
• writes the result to standard output.

The first line contains two integers $n$ and $m$ separated by a single space ($2 \le n \le 200\,000$, $0 \le m \le 500\,000$), the number of cities and the number of roads in Byteland. The cities are numbered from $1$ to $n$; Bytetown is city $1$ and Bitcity is city $n$.

Each of the following $m$ lines describes one road with three space-separated integers $a$, $b$, $c$ ($1 \le a, b \le n$, $a \ne b$, $1 \le c \le 1\,000$), meaning there is a bidirectional road of length $c$ between city $a$ and city $b$.

Print a single integer: the length of the shortest odd-length route from Bytetown to Bitcity. The route may visit cities and roads multiple times. You may change the direction of travel (including turning back) only at a city. If no such route exists, print $0$.