Find The Shortest Path 3

Du erhältst eine Karte mit n Städten und m bidirektionalen Straßen, die diese Städte miteinander verbinden. Jede Straße hat eine nichtnegative ganzzahlige Länge, angegeben durch . Deine Aufgabe ist es, die Länge des kürzesten Wegs zwischen der Stadt 1 und der Stadt n zu bestimmen.

Eingabe

Die erste Zeile enthält zwei durch Leerzeichen getrennte Ganzzahlen, n und m (), welche die Anzahl der Städte bzw. die Anzahl der Straßen angeben.

Die nächsten m Zeilen enthalten jeweils drei durch Leerzeichen getrennte Ganzzahlen , und , die eine Straße zwischen den Städten und mit der Länge beschreiben ().

Ausgabe

Gib eine einzige Ganzzahl aus, die die Länge des kürzesten Pfads von Stadt 1 zu Stadt n angibt.

Beispiele