"Лабиринт знаний"
В ЛКШ построили аттракцион "Лабиринт знаний". Лабиринт
представляет собой N комнат, занумерованных от 1 до N,
между некоторыми из которых есть двери. Когда человек проходит
через дверь, показатель его знаний изменяется на определенную
величину, фиксированную для данной двери. Вход в лабиринт
находится в комнате 1, выход - в комнате N. Каждый ЛКШонок
проходит лабиринт ровно один раз и попадает в группу в зависимости
от набранных знаний (при входе в лабиринт этот показатель равен нулю).
Ваша задача показать наилучший результат.
Входные данные. Первая строка входного файла содержит целые числа N
(1 <= N <= 2000) - количество комнат и M (1 <= M <= 10000) -
количество дверей. В каждой из следующих M строк содержится описание
двери - номера комнат, из которой она ведет и в которую она ведет,
а также целое число, которое прибавляется к количеству знаний при
прохождении через дверь (это число по модулю не превышает 10000).
Двери могут вести из комнаты в нее саму, между двумя комнатами
может быть более одной двери.
Выходные данные. В выходной файл выведите ":)" - если можно получить
неограниченно большой запас знаний, ":(" -
если лабиринт пройти нельзя, и максимальное количество
набранных знаний в противном случае.
Пример.
Входные данные:
2 2
1 2 5
1 2 -5
Выходные данные:
5
|
