Considere una red compuesta por ~n~ computadoras y ~m~ conexiones. Cada conexión especifica la velocidad a la que una computadora puede enviar datos a otra. Kotivalo desea descargar datos de un servidor. ¿Cuál es la velocidad máxima a la que puede hacerlo utilizando las conexiones de la red?

Entrada

La primera línea de entrada contiene dos enteros ~n~ y ~m~: el número de computadoras y conexiones. Las computadoras están numeradas ~1, 2, \ldots n~. La computadora ~1~ es el servidor y la computadora ~n~ es la computadora de Kotivalo. Después, hay ~m~ líneas que describen las conexiones. Cada línea contiene tres enteros ~a, b~ y ~c~: la computadora a puede enviar datos a la computadora ~b~ a una velocidad ~c~.

Salida

Imprima un entero: la velocidad máxima a la que Kotivalo puede descargar datos.

Restricciones

• ~1 \leq n \leq 500~
• ~1 \leq m \leq 1000~
• ~1 \leq a,b \leq n~
• ~1 \leq c \leq 10^9~

Ejemplo de Entrada

4 5
1 2 3
2 4 2
1 3 4
3 4 5
4 1 3

Ejemplo de Salida

6