Farmer John revisa diligentemente a las vacas cada día. Recorre algunos de los $M$ $(1 \le M \le 50,000)$ senderos, numerados $1,\ldots,M$, desde el pasto $1$ hasta el pasto $N$ (un viaje siempre posible en los mapas de senderos de los datos de prueba). Los $N$ $(1 \le N \le 10,000)$ pastos de la granja de Farmer John, numerados $1,\ldots,N$, están conectados actualmente por senderos de tierra bidireccionales. Cada sendero $i$ conecta los pastos $P1_{i}$ y $P2_{i}$ $(1 \le P1_i \le N; 1 \le P2_i \le N)$ y requiere $T_{i}$ $(1 \le T_{i} \le 1,000,000)$ unidades de tiempo para recorrerlo.

Quiere renovar algunos senderos de su granja para ahorrar tiempo en su largo viaje. En concreto, elegirá $K$ $(1 \le K \le 20)$ senderos para convertirlos en carreteras, lo que reducirá efectivamente su tiempo de recorrido a $0$. Ayuda a FJ a decidir qué senderos renovar para minimizar el tiempo necesario para ir del pasto $1$ al $N$.

Entrada

• Línea 1: tres enteros separados por espacios: $N$, $M$ y $K$.

• Líneas $2,\ldots,M+1$: la línea $i+1$ describe el sendero $i$ con tres enteros separados por espacios: $P1_{i}$, $P2_{i}$ y $T_{i}$.

Salida

• Línea 1: la longitud del camino más corto después de renovar como máximo $K$ aristas.

Ejemplos

Entrada 1

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

Salida 1

1

Nota

$K$ es $1$; renueva el sendero $3->4$ para que tarde $0$ en lugar de $100$. El nuevo camino más corto es $1->3->4$ y el tiempo total de recorrido ahora es $1$.

Autor del problema: Percy Liang, 2008