Binary Roads

Ali is on a trip and wants to reach one particular place as fast as he can.

Treat the area as a graph with $N$ places and $E$ roads. The places are numbered from $0$ to $N-1$ and every road is bidirectional. Walking one road takes 1 hour, and Ali may pass through the same place or the same road any number of times.

Ali starts at place $0$ and his destination is place $N-1$.

Every road carries a value of $0$ or $1$, and Ali carries a value of $0$ or $1$ as well. Ali may walk a road only when the value of the road equals his own value. His value flips as soon as he finishes walking a road: $0$ becomes $1$ and $1$ becomes $0$. It flips again after the next road.

Ali chooses his starting value himself. He may start with $0$ or with $1$. Find the shortest time in hours that he needs to reach place $N-1$.

The first line contains two integers $N$ and $E$ ($1 \le N \le 200\,000$, $0 \le E \le 1\,000\,000$).

Each of the next $E$ lines contains three integers $A$, $B$ and $V$. They describe a bidirectional road between place $A$ and place $B$ whose value is $V$. No two roads join the same pair of places with the same value.

For every road, $A \ne B$, $0 \le A, B < N$, and $V$ is $0$ or $1$.

Print one integer, the shortest time in hours for Ali to reach place $N-1$. Print -1 if he cannot reach it.

Ali may walk through a place or a road again, so a detour taken only to change his value is allowed. A road that leads straight to the destination is unusable at a moment when his value differs from the value of that road.