| Codeforces Testing Round 4 |
|---|
| Закончено |
Дом улыбок создан, чтобы повышать настроение. В нем есть 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, длина последовательности. Заметим, что минимальная возможная длина равна двум.
