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

Тот же лабиринт, что в классной задаче G, но требуется наименьший возможный запас знаний на выходе.

Знак меняется во всех рассуждениях сразу. Теперь :( по-прежнему означает «дойти нельзя», а :) — что знания можно сделать сколь угодно малыми, то есть отрицательными без предела.

Менять знаки весов уже не нужно: Форд — Беллман и так минимизирует. Условие бесконечности — отрицательный цикл, достижимый из комнаты 1, из которого достижима комната $n$.

Задача решается тем же кодом, что классная, только без двух смен знака. Если у вас классная решена, эта пишется за минуту — и это хороший повод убедиться, что вы не зашили знак куда-то ещё.

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

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

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