이진 도로

알리는 여행 중이고, 목적지 한 곳에 되도록 빨리 닿으려고 한다.

여행지는 장소 $N$개와 도로 $E$개로 이루어진 그래프다. 장소에는 $0$번부터 $N-1$번까지 번호가 붙어 있고, 모든 도로는 양방향이다. 도로 하나를 지나는 데 1시간이 걸리며 같은 장소와 같은 도로를 몇 번이든 다시 지날 수 있다.

알리는 $0$번 장소에서 출발해 $N-1$번 장소로 가려고 한다.

모든 도로에는 $0$ 또는 $1$의 값이 붙어 있고, 알리도 $0$ 또는 $1$의 값을 지닌다. 알리는 자신의 값과 같은 값이 붙은 도로만 지날 수 있다. 도로 하나를 지나고 나면 알리의 값은 곧바로 뒤집힌다. $0$이었으면 $1$이 되고, $1$이었으면 $0$이 된다. 다음 도로를 지난 뒤에도 또 뒤집힌다.

출발할 때의 값은 알리가 직접 고른다. $0$으로 시작해도 되고 $1$로 시작해도 된다. 알리가 $N-1$번 장소에 닿는 데 걸리는 가장 짧은 시간을 시간 단위로 구하라.

첫째 줄에 정수 $N$과 $E$가 주어진다. ($1 \le N \le 200\,000$, $0 \le E \le 1\,000\,000$)

다음 $E$개 줄에는 정수 $A$, $B$, $V$가 주어진다. $A$번 장소와 $B$번 장소를 잇는 값 $V$의 양방향 도로가 있다는 뜻이다. 같은 두 장소를 잇는 도로 가운데 값이 같은 것이 둘 이상 주어지는 일은 없다.

모든 도로에 대해 $A \ne B$, $0 \le A, B < N$이고 $V$는 $0$ 또는 $1$이다.

알리가 $N-1$번 장소에 닿는 데 걸리는 가장 짧은 시간을 정수 하나로 출력한다. 닿을 수 없으면 -1을 출력한다.

알리는 같은 장소와 같은 도로를 다시 지날 수 있으므로, 값만 바꾸려고 일부러 돌아가도 된다. 목적지로 바로 이어지는 도로가 있어도 그 순간 알리의 값이 도로의 값과 다르면 그 도로는 쓸 수 없다.