Bessie przeniosła się na małą farmę i czasem wraca do jednej z najlepszych przyjaciółek. Lubi krajobraz i nie chce zbyt szybko dotrzeć do starego domu, więc wybiera drugą najkrótszą drogę. Wie, że istnieje.

Jest $R$ dwukierunkowych dróg ($1 \le R \le 100,000$), każda łączy dwa z $N$ skrzyżowań ($1 \le N \le 5000$), numerowanych $1..N$. Zaczyna w 1, przyjaciółka i cel są w $N$.

Druga droga może dzielić drogi z dowolną najkrótszą i zawracać, powtarzając drogę czy skrzyżowanie. To najkrótsza dłuższa od najkrótszych. Gdy najkrótszych jest kilka, jest dłuższa od nich, lecz nie od jakiejkolwiek innej drogi.

Wejście

Wiersz 1: dwie liczby całkowite oddzielone spacją, $N$ i $R$.

Wiersze $2..R+1$: trzy całkowite oddzielone spacją $A$, $B$, $D$, droga między $A$ i $B$ długości $D$ ($1 \le D \le 5000$).

Wyjście

Wiersz 1: długość drugiej najkrótszej drogi z 1 do $N$.

Przykład

Wejście 1

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

Wyjście 1

450

Uwagi

Wskazówka

Dwie trasy: $1 \to 2 \to 4$ (długość $100+200=300$) i $1 \to 2 \to 3 \to 4$ (długość $100+250+100=450$).