G. Лабиринт знаний

В лабиринте $n$ комнат и $m$ односторонних дверей. Проход через дверь меняет запас знаний на заданную величину — возможно, отрицательную. Вход в комнате 1, выход в комнате $n$, начальный запас знаний ноль. Пройти лабиринт нужно один раз, но маршрут может быть каким угодно, в том числе с возвратами.

Выведите наибольший возможный запас знаний на выходе.

Ответов три:

• :) — знания можно набрать сколь угодно большие;
• :( — из комнаты 1 до комнаты $n$ дойти нельзя;
• иначе само число.

Первая строка содержит числа $n$ ($1 \le n \le 2000$) и $m$ ($1 \le m \le 10^4$).

Далее идут $m$ строк: номер комнаты, откуда ведёт дверь, куда она ведёт и изменение знаний (по модулю не больше $10^4$). Возможны петли и кратные двери.

Либо :), либо :(, либо одно число.