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\le n\le {10}^5$.
• $1\le m\le 2\cdot {10}^5$.
• $1\le a,b\le n$.
• $1\le c\le {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