Considere un grafo dirigido ponderado con ~n~ nodos y ~m~ aristas. Su tarea consiste en calcular la longitud mínima del camino del nodo ~1~ al nodo ~n~ con exactamente ~k~ aristas.

Entrada

La primera línea de entrada contiene tres enteros ~n, m~ y ~k~: el número de nodos y aristas, y la longitud del camino. Los nodos se numeran ~1,2,\dots,n~. Luego, hay ~m~ líneas que describen las aristas. Cada línea contiene tres enteros ~a, b~ y ~c~: hay una arista del nodo ~a~ al nodo ~b~ con peso ~c~.

Salida

Imprima la longitud mínima del camino. Si no existen tales caminos, imprima -1.

Restricciones

• ~1 \leq n \leq 100~
• ~1 \leq m \leq n(n-1)~
• ~1 \leq k \leq 10^9~
• ~1 \leq a,b \leq n~
• ~1 \leq c \leq 10^9~

Ejemplo de Entrada

3 4 8
1 2 5
2 3 4
3 1 1
3 2 2

Ejemplo de Salida

27