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
Entrada | Salida |
5 5
1 2 5
1 3 2
4 5 10
4 3 6
1 5 9 | 5 2 6 9 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB