Участникам сборов подарили билеты на аттракцион «Лабиринт знаний». Лабиринт
представляет собой N комнат, занумерованных от 1 до N,
между некоторыми из которых есть двери. Когда человек проходит
через дверь, показатель его знаний изменяется на определенную
величину, фиксированную для данной двери. Вход в лабиринт
находится в комнате 1, выход — в комнате N.
Каждый участник сборов
проходит лабиринт ровно один раз и наибрает некоторое количество знаний
(при входе в лабиринт этот показатель равен нулю).
Ваша задача — показать наилучший результат.
Формат входного файла
Первая строка входного файла содержит целые числа N — количество комнат и M —
количество дверей. В каждой из следующих M строк содержится описание
двери — номера комнат, из которой она ведет и в которую она ведет
(через дверь в лабиринте можно ходить только в одну сторону),
а также целое число, которое прибавляется к количеству знаний при
прохождении через дверь (это число по модулю не превышает 10000).
Двери могут вести из комнаты в нее саму, между двумя комнатами
может быть более одной двери.
Формат выходного файла
В выходной файл выведите :) — если можно получить
неограниченно большой запас знаний, :( —
если лабиринт пройти нельзя, и максимальное количество
набранных знаний в противном случае.
