L'Intensità del Traffico
Ci sono
n città, collegate da m strade. Ogni strada rappresenta una rotta di trasporto e ha un valore di intensità di traffico che indica il livello di congestione.Il tuo compito è di determinare, per ogni città
i, la minima possibile congestione di transito dalla città 1 alla città i. La congestione di transito di un percorso è definita come il valore massimo di intensità di traffico che si incontra lungo tale percorso.Input
La prima riga contiene due numeri interi separati da spazio,
n e m (), che rappresentano rispettivamente il numero di città e il numero di strade.Le successive
m righe contengono ciascuna tre interi separati da spazio e (), che indicano una strada tra le città e con intensità di traffico .Output
Bisogna stampare una singola riga contenente
n-1 interi separati da spazio, dove l'i-esimo intero rappresenta la minima congestione di transito possibile dalla città 1 alla città i+1.Esempi
Input | Output |
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