Задача Z2. You weak pathetic fool! ≡

Условие

Лю Кан проходит башни смертельных поединков. Каждая башня представляет собой испытание, в котором он может провести любое количество боёв — выигрывая или проигрывая, и накапливая общий счёт "поражения минус победы".

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

Лю Кан может сам выбирать порядок, в котором будет проходить башни. Однако если существует последовательность переходов, позволяющая бесконечно уменьшать разность "поражения минус победы", то считается, что Лю Кан обретает бесконечную силу.

Формат входных данных

Первая строка входного файла содержит два целых числа n и m — количества башен и переходов между ними соответственно. Далее идут m строк, в каждой из которых указаны три целых числа через пробел:

• u и v — номера башен, которые соединяют переход.
• w — разность победы минус поражения, необходимая для перехода между башнями u и v.

Формат выходных данных

Ограничения

n ≤ 100,

0 ≤ m ≤ n².

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

5 8
1 2 4
1 3 2
2 3 3
2 4 2
2 5 4
3 4 -1
4 5 2
5 2 1

no