En el país de Grafonia hay \(N\) ciudades numeradas del \(1\) al \(N\) y \(M\) caminos bidireccionales que las conectan. Cada camino tiene un estado de conservación:

• \(0 \rightarrow\) en buen estado, se puede usar libremente.
• \(1 \rightarrow\) en mal estado, hay que repararlo antes de usarlo.

Vos sos el ministro de obras públicas de Grafonia y querés viajar desde la ciudad \(1\) hasta la ciudad \(N\). Tu objetivo es determinar la mínima cantidad de caminos en mal estado que se deben reparar para que el viaje sea posible, o informar si no existe ningún recorrido posible incluso reparando todos los caminos.

Entrada

La primera línea contiene dos enteros \(N\) y \(M\) (\(2 \leq N \leq 10^5\), \(0 \leq M \leq 2 \cdot 10^5\)), el número de ciudades y el número de caminos, respectivamente. Las siguientes \(M\) líneas contienen tres enteros \(u\), \(v\) y \(e\) (\(1 \leq u, v \leq N\), \(e \in \{0, 1\}\)), indicando que existe un camino bidireccional entre la ciudad \(u\) y la ciudad \(v\) con estado \(e\).

Salida

Imprimir un único entero que indique la mínima cantidad de caminos en mal estado que hay que reparar para ir de la ciudad \(1\) a la ciudad \(N\), o imprimir \(-1\) si no hay manera de llegar.

Ejemplo

Entrada 1

5 7
1 2 0
2 3 0
1 3 1
1 4 1
4 3 0
4 5 1
3 5 0

Salida 1

0

Entrada 2

5 7
1 2 0
2 3 0
1 3 1
1 4 1
4 3 0
4 5 1
3 5 1

Salida 2

1