Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Ennätys

Ennätys


View task | Model solution | Statistics


Ennätys

Time limit:1.00 s
Memory limit:128 MB

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.

Tuloste

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

Rajat
Esimerkki

Syöte:
3 4
1 2 5
2 3 -2
1 3 2
2 1 -7


Tuloste:
3