Bessie mudou-se a uma pequena fazenda e às vezes volta para visitar uma melhor amiga. Gosta da paisagem e não quer chegar cedo demais à antiga casa, então escolhe o segundo menor caminho. Sabe que existe.

Há $R$ estradas bidirecionais ($1 \le R \le 100,000$), cada uma entre dois dos $N$ cruzamentos ($1 \le N \le 5000$), numerados $1..N$. Começa em 1 e a amiga, destino, está em $N$.

O segundo caminho pode compartilhar estradas com qualquer menor e voltar, repetindo estradas ou cruzamentos. É o menor entre os estritamente mais longos que os mínimos. Se há vários mínimos, é mais longo que eles mas não que qualquer outro caminho.

Entrada

Linha 1: dois inteiros separados por espaço, $N$ e $R$.

Linhas $2..R+1$: três inteiros separados por espaço $A$, $B$, $D$, estrada entre $A$ e $B$ de comprimento $D$ ($1 \le D \le 5000$).

Saída

Linha 1: comprimento do segundo menor caminho de 1 a $N$.

Exemplos

Entrada 1

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

Saída 1

450

Nota

Dica

Duas rotas: $1 \to 2 \to 4$ (comprimento $100+200=300$) e $1 \to 2 \to 3 \to 4$ (comprimento $100+250+100=450$).