Задача G. Лабиринт знаний

Автор:Зимние сборы 2005   Ограничение времени:2 сек
Входной файл:maze.in   Ограничение памяти:64 Мб
Выходной файл:maze.out  

Условие

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

Формат входного файла

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

Формат выходного файла

В выходной файл выведите :) — если можно получить неограниченно большой запас знаний, :( — если лабиринт пройти нельзя, и максимальное количество набранных знаний в противном случае.

Ограничения

1 ≤ N ≤ 2000 1 ≤ M ≤ 10000

Примеры тестов

Входной файл (maze.in) Выходной файл (maze.out)
1
2 2
1 2 5
1 2 -5
5

0.047s 0.009s 15