Descripción

La princesa Ciruela Gasa ha sido secuestrada por el temible Bizcocho. Antes de ser escondida por completo, la princesa lanzó al aire su última estrella de la suerte. La estrella surcó los cielos antes de aterrizar a los pies del amor de la princesa, Earl Gray. Earl metió la estrella en su en su bolsillo. Se dijo a sí mismo que encontraría a la princesa, incluso si eso significaba buscar todos los reinos de la tierra.

Hay ~n~ reinos repartidos por todo el país, numerados del ~1~ al ~n~. También hay una serie de ~m~ caminos bidireccionales: cada camino conecta un par de reinos y tarda cierto tiempo en recorrerlo. La estrella de la suerte que Earl recibió de la princesa es un artefacto que puede activar como máximo una vez, en cualquier punto de su recorrido. Si Earl usa la estrella de la suerte mientras está en el reino ~i~, entonces será instantáneamente transportado al reino ~n - i + 1~.

Earl se encuentra actualmente en el reino ~1~, pero no sabe adónde se han llevado a la princesa. Para cada índice ~i~ de ~2~ a ~n~, Earl desea saber el tiempo más corto que tardará en viajar del reino ~1~ al reino ~i~.

Tarea

Determina cuánto tardará Earl en ir del reino 1 a cada uno de los demás reinos de la tierra. Nótese que cada uno de estos viajes debe evaluarse independientemente, y que Earl tiene una estrella de la suerte que puede usarse como máximo una vez por viaje.

Entrada

La primera línea de entrada contiene dos enteros, ~n~ y ~m~, que representan el número de reinos y el número de caminos, respectivamente. Cada una de las m líneas siguientes contiene tres enteros, u, v y w, que indican que existe un camino que conecta los reinos ~u~ y ~v~ y que tarda ~w~ minutos en recorrer.

La entrada garantiza que nunca existirá una carretera que conecte un reino consigo mismo, ni tampoco existirá más de una carretera que conecte el mismo par de reinos.

Salida

Salida de una línea de ~n - 1~ enteros: para cada índice ~i~ de ~2~ a ~n~, la menor cantidad de tiempo en minutos que tardará Earl en viajar del reino ~1~ al reino ~i~. Si Earl no puede llegar a un reino, imprime ~-1~.

Restricciones

• ~n~ (~2 \le n \le 10^5~)
• ~m~ (~1 \le m \le 10^5~)
• ~u~ (~1 \le u \le n~)
• ~v~ (~1 \le v \le n~) = ~w~ (~1 \le w \le 10^9~)

Ejemplos de entrada y salida

Ejemplo de Entrada #1

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

Ejemplo de Salida #1

3 2 2 3 0

Ejemplo de Entrada #2

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

Ejemplo de Salida #2

-1 -1 -1 0