Вы играете в игру, состоящую из n комнат и m туннелей. Ваш начальный счет равен 0, и каждый туннель увеличивает его на x, где x может быть как положительным, так и отрицательным. Вы можете пройти через туннель несколько раз.
Ваша задача — пройти из комнаты 1 в комнату n. Какое максимальное количество очков Вы можете получить?
В первой строке находятся два целых числа n(1≤n≤2500) и m(1≤m≤5000): количество комнат и тоннелей. Комнаты пронумерованы 1,2,…,n.
Далее идет m строк, описывающих туннели. В каждой строке есть три целых числа a, b(1≤a,b≤n) и x(−109≤x≤109): туннель начинается в комнате a, заканчивается в комнате b и увеличивает ваш счет на x. Все тоннели односторонние.
Известно, что из комнаты 1 можно попасть в комнату n.
Выведите одно целое число: наибольшее количество очков, которое можно получить. Однако, если Вы можете получить сколь угодно большое количество очков, то выведите −1.