Найвищий бал.

Ви граєте в гру, яка складається з $n$ кімнат і $m$ тунелів. Ваш початковий рахунок дорівнює $0$, і кожен тунель додає до нього значення $x$, яке може бути як додатним, так і від'ємним. Ви можете проходити через один і той самий тунель кілька разів.

Ваше завдання — дістатися з кімнати $1$ до кімнати $n$. Яку максимальну кількість очок Ви можете отримати?

Вхідні дані

Перший рядок містить два цілі числа $n(1\le n\le 2500)$ і $m(1\le m\le 5000)$: кількість кімнат і тунелів. Кімнати пронумеровані від $1$ до $n$.

Наступні $m$ рядків описують тунелі. Кожен рядок містить три цілі числа $a$, $b(1\le a,b\le n)$ і $x(-10^9\le x\le 10^9)$: тунель починається в кімнаті $a$, закінчується в кімнаті $b$ і збільшує ваш рахунок на $x$. Усі тунелі є односторонніми.

Відомо, що з кімнати $1$ можна дістатися до кімнати $n$.

Вихідні дані

Виведіть одне ціле число: максимальну кількість очок, яку можна отримати. Якщо ж існує можливість отримати нескінченно велику кількість очок, виведіть $-1$.

Приклади