Bessie переехала на маленькую ферму и иногда возвращается к одной из лучших подруг. Ей нравится пейзаж, поэтому она не хочет быстро попасть в старый дом и выбирает второй кратчайший путь вместо кратчайшего. Она знает, что он существует.

Есть $R$ двусторонних дорог ($1 \le R \le 100,000$), каждая связывает два из $N$ перекрёстков ($1 \le N \le 5000$), с номерами $1..N$. Bessie начинает в1, подруга и цель находятся в $N$.

Второй путь может использовать дороги любого кратчайшего и возвращаться, повторяя дорогу или перекрёсток. Это кратчайший среди строго более длинных, чем кратчайшие. Если кратчайших несколько, он длиннее них, но не длиннее любого другого пути.

Входные данные

Строка1: два целых через пробел, $N$ и $R$.

Строки $2..R+1$: три целых через пробел, $A$, $B$, $D$, дорога между $A$ и $B$ длиной $D$ ($1 \le D \le 5000$).

Выходные данные

Строка1: длина второго кратчайшего пути от1 до $N$.

Примеры

Входные данные 1

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

Выходные данные 1

450

Примечание

Подсказка

Два маршрута: $1 \to 2 \to 4$ (длина $100+200=300$) и $1 \to 2 \to 3 \to 4$ (длина $100+250+100=450$).