Вы играете в игру, состоящую из комнат и туннелей. Ваш начальный счет равен , и каждый туннель увеличивает его на , где может быть как положительным, так и отрицательным. Вы можете пройти через туннель несколько раз.
Ваша задача — пройти из комнаты в комнату . Какое максимальное количество очков Вы можете получить?
В первой строке находятся два целых числа и : количество комнат и тоннелей. Комнаты пронумерованы .
Далее идет строк, описывающих туннели. В каждой строке есть три целых числа , и : туннель начинается в комнате , заканчивается в комнате и увеличивает ваш счет на . Все тоннели односторонние.
Известно, что из комнаты можно попасть в комнату .
Выведите одно целое число: наибольшее количество очков, которое можно получить. Однако, если Вы можете получить сколь угодно большое количество очков, то выведите .