Bessie se mudó a una pequeña granja y a veces regresa a ver a una mejor amiga. Le gusta el paisaje y no quiere llegar demasiado pronto a su antigua casa, así que elige el segundo camino más corto. Sabe que existe.

Hay $R$ carreteras bidireccionales ($1 \le R \le 100,000$), cada una entre dos de $N$ cruces ($1 \le N \le 5000$), numerados $1..N$. Empieza en 1 y su amiga, el destino, está en $N$.

El segundo camino puede compartir carreteras con cualquiera de los más cortos y retroceder, repitiendo carreteras o cruces. Es el más corto de longitud estrictamente mayor que los mínimos. Si hay varios mínimos, es más largo que ellos pero no que cualquier otro camino.

Entrada

Línea 1: dos enteros separados por espacio, $N$ y $R$.

Líneas $2..R+1$: tres enteros separados por espacio $A$, $B$, $D$, carretera entre $A$ y $B$ de longitud $D$ ($1 \le D \le 5000$).

Salida

Línea 1: longitud del segundo camino más corto de 1 a $N$.

Ejemplos

Entrada 1

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

Salida 1

450

Nota

Pista

Dos rutas: $1 \to 2 \to 4$ (longitud $100+200=300$) y $1 \to 2 \to 3 \to 4$ (longitud $100+250+100=450$).