Der zweitkürzeste Pfad
Dir werden
n Städte und m bidirektionale Straßen gegeben, die diese Städte miteinander verbinden. Jede dieser Straßen hat eine bestimmte Länge . Emil, ein abenteuerlustiger Reisender, möchte von Stadt 1 zur Stadt n reisen. Allerdings hat er eine besondere Vorgabe: Er sucht unter allen möglichen Wegen, die strikt länger sind als der kürzeste Gesamtweg, den kürzesten davon aus.Mit anderen Worten, deine Aufgabe ist es, Emil bei der Bestimmung der Länge des zweitkürzesten Pfads von Stadt
1 nach Stadt n zu helfen.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n und m, die die Anzahl der Städte bzw. die Anzahl der Straßen angeben.
Die folgenden m Zeilen enthalten jeweils drei ganze Zahlen , und , was bedeutet, dass es eine bidirektionale Straße zwischen der Stadt und der Stadt mit der Länge gibt.Ausgabe
Gib eine einzelne ganze Zahl aus, die die Länge des zweitkürzesten Pfads von Stadt
1 nach Stadt n angibt.Beispiele
Eingabe | Ausgabe |
6 7
1 2 3
2 3 4
3 6 5
2 6 9
1 4 3
4 5 8
5 6 2
| 13 |
Constraints
Time limit: 5.4 seconds
Memory limit: 512 MB
Output limit: 1 MB