Die Verkehrsintensität
Es gibt
n Städte, die durch m Straßen miteinander verbunden sind. Jede dieser Straßen stellt eine Transportroute dar und besitzt einen Verkehrsintensitätswert , der den Grad der Stau- bzw. Auslastung abbildet.Ihre Aufgabe besteht darin, für jede Stadt
i die geringstmögliche Transitbelastung von Stadt 1 zu Stadt i zu ermitteln. Dabei wird die Transitbelastung eines Pfads als der höchste auftretende Wert der Verkehrsintensität entlang dieses Pfads definiert.Eingabe
Die erste Zeile enthält zwei durch Leerzeichen getrennte ganze Zahlen,
n und m (), die die Anzahl der Städte bzw. die Anzahl der Straßen angeben.In den folgenden
m Zeilen stehen jeweils drei durch Leerzeichen getrennte ganze Zahlen und (). Sie beschreiben eine Straße zwischen den Städten und mit der Verkehrsintensität .Ausgabe
Geben Sie in einer einzelnen Zeile
n-1 durch Leerzeichen getrennte ganze Zahlen aus. Das i-te dieser Zahlen ist die minimale Transitbelastung von Stadt 1 zu Stadt i+1.Beispiele
Eingabe | Ausgabe |
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