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