Вы играете в игру, состоящую из $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$.