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