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