Bessie a déménagé dans une petite ferme et aime parfois retourner voir une de ses meilleures amies. Elle aime le paysage et ne veut pas arriver trop vite à son ancien chez-elle, donc choisit le deuxième plus court chemin. Elle sait qu’il existe.

Il y a $R$ routes bidirectionnelles ($1 \le R \le 100,000$), chacune reliant deux des $N$ intersections ($1 \le N \le 5000$), numérotées $1..N$. Elle part de 1 et son amie, la destination, est à $N$.

Le deuxième chemin peut partager des routes avec n’importe quel plus court et revenir en arrière, réutilisant routes ou intersections. Il est le plus court de ceux strictement plus longs que les plus courts. S’il y en a plusieurs, il est plus long qu’eux, mais pas plus long qu’un autre chemin.

Entrée

Ligne 1 : deux entiers séparés par un espace, $N$ et $R$.

Lignes $2..R+1$ : trois entiers séparés par un espace $A$, $B$, $D$ décrivant la route entre $A$ et $B$ de longueur $D$ ($1 \le D \le 5000$).

Sortie

Ligne 1 : longueur du deuxième plus court chemin de 1 à $N$.

Exemples

Entrée 1

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

Sortie 1

450

Remarque

Indice

Deux itinéraires : $1 \to 2 \to 4$ (longueur $100+200=300$) et $1 \to 2 \to 3 \to 4$ (longueur $100+250+100=450$).