Bessie si è trasferita in una piccola fattoria e talvolta torna a visitare una migliore amica. Ama il paesaggio e non vuole arrivare troppo presto alla vecchia casa, quindi sceglie il secondo percorso più breve. Sa che esiste.

Ci sono $R$ strade bidirezionali ($1 \le R \le 100,000$), ciascuna fra due dei $N$ incroci ($1 \le N \le 5000$), numerati $1..N$. Parte da 1 e l’amica, destinazione, è a $N$.

Il secondo percorso può condividere strade con qualsiasi minimo e tornare indietro, ripetendo strade o incroci. È il più breve fra quelli strettamente più lunghi dei minimi. Se i minimi sono diversi, è più lungo di loro ma non di qualsiasi altro percorso.

Input

Riga 1: due interi separati da spazio, $N$ e $R$.

Righe $2..R+1$: tre interi separati da spazio $A$, $B$, $D$, strada fra $A$ e $B$ di lunghezza $D$ ($1 \le D \le 5000$).

Output

Riga 1: lunghezza del secondo percorso più breve da 1 a $N$.

Esempi

Input 1

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

Output 1

450

Nota

Suggerimento

Due percorsi: $1 \to 2 \to 4$ (lunghezza $100+200=300$) e $1 \to 2 \to 3 \to 4$ (lunghezza $100+250+100=450$).