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 cij — 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?

Input

The first line contains two positive integers n and m (<image>), 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, cij и cji (1 ≤ i, j ≤ n, i ≠ j, - 104 ≤ cij, cji ≤ 104). It is guaranteed that no more than one door connects any two rooms. No door connects the room with itself.

Output

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.

Examples

Input

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


Output

4

Note

Cycle is such a sequence of rooms a1, a2, ..., ak, that a1 is connected with a2, a2 is connected with a3, ..., ak - 1 is connected with ak, ak is connected with a1. 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.
5 4
1 2 1 -1
2 3 1 -1
3 1 1 -1
4 5 2 -1
 3 3
1 2 -10 30
1 3 1 1
2 3 -10 -1
 6 15
1 2 -52 -10
1 3 2 -72
1 4 -72 -2
1 5 6 -100
1 6 -100 -97
2 3 -63 -37
2 4 -99 -55
2 5 -84 -9
2 6 -17 -8
3 4 -16 -57
3 5 -1 8
3 6 -22 -88
4 5 -59 -75
4 6 -92 -63
5 6 9 -65
 10 9
1 2 3 -5
2 3 5 -7
3 4 7 -9
4 5 8 -11
5 6 7 -10
1 6 -10 5
2 4 1 -15
4 6 1 -16
2 6 -9 1
 10 8
1 2 3 -5
2 3 5 -7
3 4 7 -9
4 5 8 -11
5 1 7 -10
4 7 -1 -1
7 8 -1 -1
8 4 -1 -1
 2 0
 2 1
1 2 10 10
 7 21
1 2 -91 -94
1 3 4 -96
1 4 -98 -100
1 5 -91 -98
1 6 -97 -29
1 7 -98 -91
2 3 -99 -98
2 4 6 -90
2 5 -96 -95
2 6 -100 -96
2 7 -94 -4
3 4 -95 -97
3 5 11 -94
3 6 -93 -91
3 7 -97 -95
4 5 -91 -93
4 6 1 -98
4 7 -92 -95
5 6 -95 -98
5 7 12 -90
6 7 -97 -99
 300 0
 5 10
1 2 -22 -3
1 3 4 -30
1 4 -30 -30
1 5 -12 -21
2 3 9 -28
2 4 9 -19
2 5 -23 7
3 4 -17 -4
3 5 -4 -21
4 5 -12 -4
 4 6
1 2 -65 -53
1 3 -64 -19
1 4 -77 -64
2 3 -20 8
2 4 -11 -61
3 4 -39 -8
 2 1
1 2 10 -10
 3 3
1 2 -10 3
1 3 1 -10
2 3 -10 -1
 10 9
1 2 3 -5
2 3 5 -7
3 4 7 -9
4 5 8 -11
5 1 7 -10
4 7 -1 -1
7 8 -1 -1
8 4 -1 -1
6 10 1 1
 1 0

2
 2
 2
 3
 5
 0
 2
 7
 0
 3
 0
 0
 3
 2
 0

// Problem: B. Smile House
// Contest: Codeforces - Codeforces Testing Round #4
// URL: https://codeforces.com/problemset/problem/147/B
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

/*
	Normie's Template v2.1
	Changes:
	Added vectorization optimizations.
*/
 
// Standard library in one include.
#include <bits/stdc++.h>
using namespace std;
 
// ordered_set library.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(el) tree<el,null_type,less<el>,rb_tree_tag,tree_order_statistics_node_update>
 
// AtCoder library. (Comment out these two lines if you're not submitting in AtCoder.) (Or if you want to use it in other judges, run expander.py first.)
//#include <atcoder/all>
//using namespace atcoder;
 
//Pragmas (Comment out these three lines if you're submitting in szkopul.)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops,tree-vectorize")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 
//File I/O.
#define FILE_IN "cseq.inp"
#define FILE_OUT "cseq.out"
#define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)
 
//Fast I/O.
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define nfio cin.tie(0);cout.tie(0)
#define endl "\n"
 
//Order checking.
#define ord(a,b,c) ((a>=b)and(b>=c))
 
//min/max redefines, so i dont have to resolve annoying compile errors.
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))

// Fast min/max assigns to use with AVX.
// Requires g++ 9.2.0.
template<typename T>
__attribute__((always_inline)) void chkmin(T& a, const T& b) {
    a=(a<b)?a:b;
}

template<typename T>
__attribute__((always_inline)) void chkmax(T& a, const T& b) {
    a=(a>b)?a:b;
}
 
//Constants.
#define MOD (ll(998244353))
#define MAX 300001
#define mag 320
const long double PI=3.14159265358979;
 
//Pairs and 3-pairs.
#define p1 first
#define p2 second.first
#define p3 second.second
#define fi first
#define se second
#define pii(element_type) pair<element_type,element_type>
#define piii(element_type) pair<element_type,pii(element_type)>
 
//Quick power of 2.
#define pow2(x) (ll(1)<<x)
 
//Short for-loops.
#define ff(i,__,___) for(int i=__;i<=___;i++)
#define rr(i,__,___) for(int i=__;i>=___;i--)
 
//Typedefs.
#define bi BigInt
typedef long long ll;
typedef long double ld;
typedef short sh;

//---------END-------//
vector<int> vec;
int n,m,i,j,k,t,t1,u,v,a,b;
int minn[301][301][9];
int cur[301][301],cur2[301][301];
int main()
{
	fio;
	cin>>n>>m;
	for (t=0;t<=8;t++)for (i=1;i<=n;i++) for (j=1;j<=n;j++) minn[i][j][t]=1e7+7;
	for (t=0;t<=8;t++)for (i=1;i<=n;i++)  minn[i][i][t]=0;
	for (i=1;i<=n;i++) for (j=1;j<=n;j++) cur[i][j]=1e7+7;
	for (i=1;i<=n;i++)  cur[i][i]=0;
	for (i=1;i<=m;i++)
	{
		cin>>u>>v>>a>>b;
		minn[u][v][0]=-a;
		minn[v][u][0]=-b;
	}
	for (t=1;t<=8;t++) 
	{
		for (i=1;i<=n;i++) for (j=1;j<=n;j++) for (k=1;k<=n;k++) 
		{
			chkmin(minn[i][k][t],minn[i][j][t-1]+minn[j][k][t-1]);
		}
	}
	for (t=8;t>=0;t--)
	{
		for (i=1;i<=n;i++) for (j=1;j<=n;j++) cur2[i][j]=1e7+7;
		for (i=1;i<=n;i++)  cur2[i][i]=0;
	//	cout<<"Attempt "<<t<<endl;
		//	for (i=1;i<=n;i++)
		//	{
		//		for (j=1;j<=n;j++) cout<<cur[i][j]<<' ';
		//		cout<<endl;
		//	}
		//	cout<<endl;
		//	for (i=1;i<=n;i++)
		//	{
		//		for (j=1;j<=n;j++) cout<<minn[i][j][t]<<' ';
		//		cout<<endl;
		//	}
		for (i=1;i<=n;i++) for (j=1;j<=n;j++) for (k=1;k<=n;k++) 
		{
			chkmin(cur2[i][k],cur[i][j]+minn[j][k][t]);
		}
		//	cout<<endl;
		//	for (i=1;i<=n;i++)
		//	{
		//		for (j=1;j<=n;j++) cout<<cur2[i][j]<<' ';
		//		cout<<endl;
		//	}
		b=1;
		for (i=1;i<=n;i++) if (cur2[i][i]<0) b=0;
		if (b)
		{
			a^=(1<<t);
			for (i=1;i<=n;i++) for (j=1;j<=n;j++) cur[i][j]=cur2[i][j];
	//		cout<<"YES "<<a<<endl;
		}
	}
	if (a>=n) cout<<-1; else cout<<a+1;
}