Задача №1881. Лабиринт знаний
Участникам сборов подарили билеты на аттракцион «Лабиринт знаний». Лабиринт представляет собой \(N\) комнат, занумерованных от \(1\) до \(N\), между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход — в комнате \(N\). Каждый участник сборов проходит лабиринт ровно один раз и набирает некоторое количество знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача — показать наилучший результат.
Первая строка входного файла содержит целые числа \(N\) (\(1\le N\le 2\,000\)) — количество комнат и \(M\) (\(1\leq M\leq 10\,000\)) — количество дверей. В каждой из следующих \(M\) строк содержится описание двери — номера комнат, из которой она ведёт и в которую она ведёт (через дверь в лабиринте можно ходить только в одну сторону), а также целое число, которое прибавляется к количеству знаний при прохождении через дверь (это число по модулю не превышает \(10\,000\)). Двери могут вести из комнаты в неё саму, между двумя комнатами может быть более одной двери.
В выходной файл выведите «:)», если можно получить неограниченно большой запас знаний, «:(», если лабиринт пройти нельзя, и максимальное количество набранных знани в противном случае.
2 2 1 2 5 1 2 -5
5