Inspirado por el nuevo parque acuático en Machu Picchu, Perú, Farmer John quiere construir uno para las vacas. Su mayor atracción será un enorme tobogán de diseño peculiar.

Tiene $E$ ($1 \le E \le 150,000$) minitoboganes entre $V$ ($2 \le V \le 50,000$) piscinas $1..V$. Solo se recorren en su dirección, nunca al revés. Las vacas parten de 1 y llegan a la final $V$. Cada piscina salvo 1 tiene al menos uno que entra; salvo $V$, al menos otro que sale.

Desde cualquier piscina se llega al final $V$. No se puede salir de una y volver a ella tras recorrer toboganes.

El tobogán $i$ va de $P_{i}$ a $Q_{i}$ ($1 \le P_{i} \le V; 1 \le Q_{i} \le V; P_{i} \ne Q_{i}$), con diversión $F_{i}$ ($0 \le F_{i} \le 2,000,000,000$). Bessie suma la diversión de todos los recorridos.

Después de tanta cola quiere divertirse al máximo. Suele elegir las salidas, pero pierde el control como máximo $K$ veces ($1 \le K \le 10$) y toma una aleatoria, incluso en 1.

¿Qué diversión garantiza si elige para maximizar el peor caso?

Ejemplo: 3 piscinas, números entre corchetes, 4 toboganes y $K$ igual a 1; diversión fuera de corchetes:

          [1]
         /   \
   5 -> /     \ <- 9
       /       \
     [2]---3---[3]
        \__5__/

Siempre va de 1 a 3. Libre, iría 1 a 2, luego por diversión 5 a 3: $5+5=10$. Perder el control en 1 puede dar directamente 3 y 9; en 2 solo $5+3 = 8$.

Elige $1\to3$ para 9. Si pierde el control en 1 y toma $1\to2$, no volverá a perderlo en 2 y obtendrá 10. Garantiza al menos 9.

Entrada

• Línea $1$: enteros $V$, $E$, $K$ separados por espacios.
• Líneas $2..E + 1$: la línea $i+1$ contiene enteros $P_{i}$, $Q_{i}$, $F_{i}$ separados por espacios.

Salida

• Línea $1$: un entero, la diversión mínima que Bessie garantiza.

Ejemplos

Entrada 1

3 4 1
2 3 5
1 2 5
1 3 9
2 3 3

Salida 1

9

Autor del problema: John Pardon, 2010