Den kürzesten Pfad finden 2
Sie haben eine Karte aus
n Städten und m bidirektionalen Straßen, die diese Städte miteinander verbinden. Jede Straße hat eine nicht-negative ganzzahlige Länge, angegeben durch . Ihre Aufgabe ist es, die Länge des kürzesten Pfades zwischen der Stadt 1 und der Stadt n zu ermitteln.Eingabe
Die erste Zeile enthält zwei durch Leerzeichen getrennte ganze Zahlen,
n und m (). Dabei steht n für die Anzahl der Städte und m für die Anzahl der Straßen.Die folgenden
m Zeilen beinhalten jeweils drei durch Leerzeichen getrennte ganze Zahlen , und , die eine Straße zwischen den Städten und mit Länge beschreiben ().Ausgabe
Geben Sie eine ganze Zahl aus, die die Länge des kürzesten Pfades von Stadt
1 zu Stadt n angibt.Beispiele
Eingabe | Ausgabe |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB