Tu tarea consiste en encontrar las ~k~ rutas de vuelo más cortas entre Syrjälä y Metsälä. Una ruta puede pasar por la misma ciudad varias veces.

Ten en cuenta que puede haber varias rutas con el mismo precio y que todas deben considerarse (consulta el ejemplo).

Entrada

La primera línea de entrada contiene tres números enteros: ~n, m~ y ~k~: el número de ciudades, el número de vuelos y el parámetro ~k~. Las ciudades están numeradas del ~1~ al ~n~. La ciudad ~1~ es Syrjälä y la ciudad ~n~ es Metsälä.

A continuación, la entrada contiene ~m~ líneas que describen los vuelos. Cada línea contiene tres números enteros: ~a, b~ y ~c~: un vuelo comienza en la ciudad ~a~, termina en la ciudad ~b~ y su precio es ~c~. Todos los vuelos son de ida.

Puedes asumir que existen al menos ~k~ rutas distintas entre Syrjälä y Metsälä.

Salida

Imprimir ~k~ enteros: los precios de las ~k~ rutas más económicas, ordenados según su precio.

Restricciones

• ~2 \leq n \leq 10^5~
• ~1 \leq m \leq 2 \cdot 10^5~
• ~1 \leq a,b \leq n~
• ~1 \leq c \leq 10^9~
• ~1 \leq k \leq 10~

Ejemplo de Entrada

4 6 3
1 2 1
1 3 3
2 3 2
2 4 6
3 2 8 
3 4 1

Ejemplo de Salida

4 4 7

Explicación: Las rutas más económicas son ~1 \rightarrow 3 \rightarrow 4~ (precio 4), ~1 \rightarrow 2 \rightarrow 3 \rightarrow 4~ (precio 4) y ~1 \rightarrow 2 \rightarrow 4~ (precio 7).