|
Лабиринт знаний
(Время: 1 сек. Память: 16 Мб Сложность: 63%)
В стране Умландии построили аттракцион "Лабиринт знаний". Лабиринт представляет собой N комнат, занумерованных от 1 до N, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход - в комнате N. Каждый ученик проходит лабиринт ровно один раз и попадает в ту или иную учебную группу в зависимости от количества набранных знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача показать наилучший результат.
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа N (1 ≤ N ≤ 2000) - количество комнат и M (0 ≤ M ≤ 10000) - количество дверей. В каждой из следующих M строк содержится описание двери - номера комнат, из которой она ведет и в которую она ведет (через дверь можно ходить только в одном направлении), а также целое число, которое прибавляется к количеству знаний при прохождении через дверь (это число по модулю не превышает 10000). Двери могут вести из комнаты в нее саму, между двумя комнатами может быть более одной двери.
Выходные данные
В выходной файл OUTPUT.TXT выведите ":)" - если можно получить неограниченно большой запас знаний, ":(" - если лабиринт пройти нельзя, и максимальное количество набранных знаний в противном случае.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 2
1 2 5
1 2 -5
| 5 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
