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 y querés viajar desde la ciudad 1 hasta la ciudad N. Estás apurado, por lo que querés recorrer el mínimo número de caminos durante el trayecto. Solo es posible pasar por caminos en buen estado, pero por suerte tenes K unidades de presupuesto para destinar a las reparaciones. Cada reparación cuesta una unidad de presupuesto, sin importar cuántas veces se use ese camino después.

Entrada

La primera línea contiene dos enteros \(N\), \(M\) y \(K\) (\(2 \leq N \leq 10^5\), \(0 \leq M \leq 2 \cdot 10^5\), \(0 \leq K \leq 20\)), el número de ciudades, el número de caminos y las unidades de presupuesto, 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 entero, el mínimo número de caminos a recorrer para ir de la ciudad 1 a la ciudad N respetando el presupuesto de reparación K, o -1 si no hay manera.

Ejemplo

Entrada 1

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

Salida 1

2

Entrada 2

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

Salida 2

3