Bessie ist auf eine kleine Farm gezogen und besucht manchmal eine ihrer besten Freundinnen im alten Zuhause. Sie mag die Landschaft und möchte nicht zu früh ankommen, daher wählt sie den zweitkürzesten Weg statt des kürzesten. Sie weiß, dass er existiert.

Es gibt $R$ bidirektionale Straßen ($1 \le R \le 100,000$), jede verbindet zwei der $N$ Kreuzungen ($1 \le N \le 5000$), nummeriert $1..N$. Sie startet bei 1, die Freundin und das Ziel sind bei $N$.

Der zweite Weg darf Straßen jedes kürzesten teilen und zurückgehen, Straßen oder Kreuzungen wiederholen. Er ist der kürzeste mit größerer Länge als die kürzesten. Bei mehreren kürzesten ist er länger als diese, aber nicht länger als irgendein anderer Weg.

Eingabe

Zeile 1: zwei durch Leerzeichen getrennte ganze Zahlen $N$ und $R$.

Zeilen $2..R+1$: drei durch Leerzeichen getrennte ganze Zahlen $A$, $B$, $D$, Straße zwischen $A$ und $B$ mit Länge $D$ ($1 \le D \le 5000$).

Ausgabe

Zeile 1: Länge des zweitkürzesten Wegs von 1 nach $N$.

Beispiele

Eingabe 1

4 4
1 2 100
2 4 200
2 3 250
3 4 100

Ausgabe 1

450

Hinweis

Hinweis

Zwei Wege: $1 \to 2 \to 4$ (Länge $100+200=300$) und $1 \to 2 \to 3 \to 4$ (Länge $100+250+100=450$).