Hay ~n~ ciudades y ~m~ conexiones aéreas entre ellas. Tu tarea es determinar la longitud de la ruta más corta desde Syrjälä a cada ciudad.

Entrada

La primera línea de entrada tiene dos números enteros ~n~ y ~m~: el número de ciudades y conexiones de vuelo. Las ciudades están numeradas ~1,2,\dots,n~, y la ciudad ~1~ es Syrjälä. A continuación, hay ~m~ líneas que describen las conexiones de vuelo. Cada línea tiene tres números enteros ~a, b~ y ~c~: un vuelo empieza en la ciudad ~a~, termina en la ciudad ~b~ y su longitud es ~c~. Cada vuelo es de ida. Se puede suponer que es posible viajar desde Syrjälä a todas las demás ciudades.

Salida

Imprime ~n~ enteros: las longitudes de las rutas más cortas desde Syrjälä a las ciudades ~1,2,\dots,n~.

Restricciones

• ~1 \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~.

Ejemplo de Entrada

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

Ejemplo de Salida

0 5 2