B. Дом улыбок
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Дом улыбок создан, чтобы повышать настроение. В нем есть n комнат. Некоторые из комнат соединены дверьми. Про каждые две комнаты (с номерами i и j), которые соединены дверью, Петя знает величину cij — на сколько изменяется у него настроение при переходе из комнаты с номером i в комнату с номером j.

Петя задумался: может ли он поднять себе настроение до бесконечности, двигаясь по какому-нибудь циклу? А если может, то какое минимальное количество комнат ему надо будет проходить за один период цикла?

Входные данные

В первой строке записаны два целых положительных числа n и m (), где n — количество комнат, а m — количество дверей в доме улыбок. Далее идет описание дверей: m строк по четыре целых числа i, j, cij и cji (1 ≤ i, j ≤ n, i ≠ j,  - 104 ≤ cij, cji ≤ 104). Гарантируется, что любые две комнаты соединяет не более одной двери. Никакая дверь не соединяет комнату саму с собой.

Выходные данные

Выведите минимальное количество комнат, которое необходимо проходить за один проход по циклу, бесконечно повышающему настроение, или число 0, если такого цикла не существует.

Примеры
Входные данные
4 4
1 2 -10 3
1 3 1 -10
2 4 -10 -1
3 4 0 -3
Выходные данные
4
Примечание

Напомним, что циклом называется такая последовательность комнат a1, a2, ..., ak, что a1 соединена с a2, a2 соединена с a3, ..., ak - 1 соединена с ak, ak соединена с a1. Некоторые элементы последовательности могут совпадать, то есть цикл не обязательно должен быть простым. Количеством комнат в цикле считается k, длина последовательности. Заметим, что минимальная возможная длина равна двум.