A8449 | Smile House

A smile house is created to raise the mood. It has $n$ rooms. Some of the rooms are connected by doors. For each two rooms (number $i$ and $j$ ), which are connected by a door, Petya knows their value $c_{ij}$ — the value which is being added to his mood when he moves from room $i$ to room $j$ .

Petya wondered whether he can raise his mood infinitely, moving along some cycle? And if he can, then what minimum number of rooms he will need to visit during one period of a cycle?

The first line contains two positive integers $n$ and $m$ (), where $n$ is the number of rooms, and $m$ is the number of doors in the Smile House. Then follows the description of the doors: $m$ lines each containing four integers $i$ , $j$ , $c_{ij}$ и $c_{ji}$ ( $1<=i,j<=n,i≠j,-10^{4}<=c_{ij},c_{ji}<=10^{4}$ ). It is guaranteed that no more than one door connects any two rooms. No door connects the room with itself.

Print the minimum number of rooms that one needs to visit during one traverse of the cycle that can raise mood infinitely. If such cycle does not exist, print number $0$ .