Smile House

题意翻译

n个点,m条边,无向图但一条无向边的两个方向的边权不同,求图上最小正环的大小(定义正环为从一个点出发再回到这个点经过所有边边权之和为正)(定义最小正环的含义为这个正环经过的点数最少) 输入格式: 第一行两个整数n,m,表示点数和边数 接下来m行,一行四个整数x,y,z,w,表示x到y有一条边,x到y的边权为z,y到x的边权为w 输出格式: 一行一个整数,表示最小正环的大小(即这个正环上点的个数),如果没有正环输出0

题目描述

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 $ (![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF147B/ce95e141666c771c9cc78c440da97c206ea2431d.png)), 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 $ .

输入输出样例

输入样例 #1

4 4
1 2 -10 3
1 3 1 -10
2 4 -10 -1
3 4 0 -3

输出样例 #1

4

说明

Cycle is such a sequence of rooms $ a_{1} $ , $ a_{2} $ , ..., $ a_{k} $ , that $ a_{1} $ is connected with $ a_{2} $ , $ a_{2} $ is connected with $ a_{3} $ , ..., $ a_{k-1} $ is connected with $ a_{k} $ , $ a_{k} $ is connected with $ a_{1} $ . Some elements of the sequence can coincide, that is, the cycle should not necessarily be simple. The number of rooms in the cycle is considered as $ k $ , the sequence's length. Note that the minimum possible length equals two.