Məsələlər
Наибольший балл
Наибольший балл
Вы играете в игру, состоящую из $n$ комнат и $m$ туннелей. Ваш начальный счет равен $0$, и каждый туннель увеличивает его на $x$, где $x$ может быть как положительным, так и отрицательным. Вы можете пройти через туннель несколько раз.
Ваша задача --- пройти из комнаты $1$ в комнату $n$. Какое максимальное количество очков Вы можете получить?
\InputFile
В первой строке находятся два целых числа $n\:(1 \le n \le 2500)$ и $m\:(1 \le m \le 5000)$: количество комнат и тоннелей. Комнаты пронумерованы $1, 2, \dots , n$.
Далее идет $m$ строк, описывающих туннели. В каждой строке есть три целых числа $a$, $b\:(1 \le a, b \le n)$ и $x\:(−10^9 \le x \le 10^9)$: туннель начинается в комнате $a$, заканчивается в комнате $b$ и увеличивает ваш счет на $x$. Все тоннели односторонние.
Известно, что из комнаты $1$ можно попасть в комнату $n$.
\OutputFile
Выведите одно целое число: наибольшее количество очков, которое можно получить. Однако, если Вы можете получить сколь угодно большое количество очков, то выведите $-1$.
Giriş verilənləri #1
4 5 1 2 3 2 4 -1 1 3 -2 3 4 7 1 4 4
Çıxış verilənləri #1
5