La intensidad de tráfico

Hay n ciudades, conectadas por m carreteras. Cada carretera representa una ruta de transporte y tiene un valor de intensidad de tráfico que indica su nivel de congestión.

Tu tarea es determinar, para cada ciudad i, la congestión de tránsito mínima posible desde la ciudad 1 hasta la ciudad i. La congestión de un camino se define como la máxima intensidad de tráfico a lo largo de ese trayecto.

Entrada

La primera línea contiene dos enteros separados por espacio, n y m (), que representan el número de ciudades y el número de carreteras, respectivamente.

Las siguientes m líneas contienen tres enteros separados por espacio y (), que representan una carretera entre las ciudades y con una intensidad de tráfico .

Salida

Imprime una sola línea que contenga n-1 enteros separados por espacio, donde el entero número i representa la congestión de tránsito mínima posible desde la ciudad 1 hasta la ciudad i+1.

Ejemplos