Bessie ha decidido sacudirse la pereza y ha decidido mejorar su forma trotando desde la granja hasta la alberca varias veces a la semana. Por supuesto, ella no quiere trabajar muy duro, por lo tanto ella planea trotar bajando hacia la alberca y luego regresar tranquilamente al establo.

Bessie tampoco quiere correr muy lejos, por lo tanto ella generalmente toma la secuencia más corta de caminos de vacas para llegar a la alberca. Cada uno de los ~M~ ~(1 \leq M \leq 10 000)~ caminos de vacas conecta dos pastizales convenientemente numerados ~1...N~ ~(1 \leq N \leq 1000)~. Aún más convenientemente, los pastizales están numerados de tal manera que si ~X > Y~ entonces el camino del pastizal ~X~ al pastizal ~Y~ es bajando. El pastizal ~N~ es el establo (en la cima de la montaña) y el pastizal ~1~ es la alberca (en la base).

Justamente después de una semana de comenzar a trotar, Bessie ha comenzado a cansarse de tomar siempre la misma ruta para llegar a la alberca. A ella le gustaría variar su ruta tomando caminos diferentes en días diferentes. Específicamente Bessie quisiera tomar exactamente ~K~ ~(1 \leq K \leq 100)~ rutas diferentes por variedad. Para evitar mucho ejercicio, ella quiere que estas sean las ~K~ rutas más cortas desde el establo a la alberca. Se consideran que dos rutas son diferentes si consisten de secuencias diferentes de caminos.

Ayude a Bessie a determinar cuán extenuante será su trabajo determinando las longitudes de cada una de las ~K~ rutas más cortas en la red de pastizales. A usted se le dará una lista de caminos de bajada de ~X_i~ a ~Y_i~ junto con la longitud de los caminos ~(1 \leq Y_i < X_i \leq N)~. El camino de vaca ~i~ tiene longitud ~D_i~ ~(1 \leq D_i \leq 1 000 000)~.

Entrada

• Línea 1: Tres enteros separados por espacio: ~N~, ~M~ y ~K~.

• Líneas 2…N: La línea ~i+1~ describe un camino de bajada usando tres enteros separados por espacios: ~X_i~, ~Y_i~ y ~D_i~.

Salida

• Líneas 1…K: La línea ~i~ contiene la longitud de la ruta \(i-ésima\) más corta o ~-1~ si no existe tal ruta. Si la longitud de una ruta más corta ocurre varias veces, esté seguro de incluir esas varias veces en la salida.

Ejemplo de Entrada

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

Ejemplo de Salida

1
2
2
3
6
7
-1

Explicación

Las rutas son (~5~-~1~), (~5~-~3~-~1~), (~5~-~2~-~1~), (~5~-~3~-~2~-~1~), (~5~-~4~-~3~-~1~), (~5~-~4~-~3~-~2~-~1~).