Juegas a un juego que consta de ~n~ habitaciones y ~m~ túneles. Su puntuación inicial es 0, y cada túnel aumenta su puntuación en ~x~, donde ~x~ puede ser tanto positivo como negativo. Puedes atravesar un túnel varias veces.

Tu tarea consiste en ir de la sala ~1~ a la sala ~n~. ¿Cuál es la puntuación máxima que puedes obtener?

Entrada

La primera línea de entrada tiene dos números enteros ~n~ y ~m~: el número de habitaciones y de túneles. Las habitaciones se numeran ~1,2,\dot ,n~. A continuación, hay m líneas que describen los túneles. Cada línea tiene tres números enteros ~a, b~ y ~x~: el túnel empieza en la sala ~a~, termina en la sala ~b~ y aumenta tu puntuación en ~x~. Todos los túneles son unidireccionales. Puedes suponer que es posible llegar de la sala ~1~ a la sala ~n~.

Salida

Imprime un entero: la puntuación máxima que puedes obtener. Sin embargo, si puedes obtener una puntuación arbitrariamente grande, imprime -1.

Restricciones

• ~1 \leq n \leq 2500~
• ~1 \leq m \leq 5000~
• ~1 \leq a,b \leq n~
• ~-10^9 \leq x \leq 10^9~

Ejemplo de Entrada

4 5
1 2 3
2 4 -1
1 3 -2
3 4 7
1 4 4

Ejemplo de Salida

5