Find The Shortest Path 1

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 nicht-negative Länge, bezeichnet durch . Deine Aufgabe besteht darin, die Länge des kürzesten Wegs zwischen Stadt 1 und Stadt n zu ermitteln.

Input

Die erste Zeile enthält zwei durch Leerzeichen getrennte ganze Zahlen, n und m (), die für die Anzahl der Städte bzw. die Anzahl der Straßen stehen.

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

Output

Das Programm soll die Länge des kürzesten Wegs von Stadt 1 nach Stadt n ausgeben.

Beispiele