- Time limit: 1.00 s
- Memory limit: 128 MB
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$
Syöte:
3 4
1 2 5
2 3 -2
1 3 2
2 1 -7
Tuloste:
3