Pelaat peliä, jossa on $n$ huonetta ja niiden välillä $m$ käytävää. Sinulla on aluksi 0 pistettä, ja jokaista käytävää kulkeminen kasvattaa tai vähentää pistemäärää tietyllä tavalla. Voit kulkea samaa käytävää monta kertaa.

Kuinka monta pistettä voit kerätä, kun aloitat huoneesta 1 ja sinun tulee lopettaa huoneeseen $n$?

Syöte

Syötteen alussa on kokonaisluvut $n$ ja $m$: huoneiden määrä ja käytävien määrä. Huoneet on numeroitu kokonaisluvuin $1,2,\ldots,n$.

Sitten syötteessä on $m$ riviä, jotka kuvaavat käytävät. Jokaisella rivillä on kolme kokonaislukua $a$, $b$ ja $c$: käytävä lähtee huoneesta $a$, johtaa huoneeseen $b$ ja sitä kulkemalla saa $c$ pistettä. Jokainen käytävä on yksisuuntainen.

Voit olettaa, että on mahdollista päästä huoneesta $1$ huoneeseen $n$.

Tuloste

Tulosta yksi kokonaisluku: montako pistettä voit kerätä korkeintaan. Jos voit kerätä äärettömästi pisteitä, tulosta kuitenkin "QAQ".

Rajat

• $1 \le n \le 1000$
• $1 \le m \le 2000$
• $1 \le a,b \le n$
• $-10^9 \le c \le 10^9$

Esimerkki

Syöte:

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

Tuloste:

3