#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
ll rd() {
	ll rt = 0, f = 1;
	char c = getchar();
	while ('0' > c || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') rt = rt * 10 + c - 48, c = getchar();
	return rt * f;
}
void wr(ll x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) wr(x / 10);
	putchar(x % 10 + 48);
	return ;
}
int n;
struct Maxtir {
	int m[301][301];
	int *operator [](int i) {
		return m[i];
	}
	const int *operator [](int i) const {
		return m[i];
	}
	void init() {
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j)
				m[i][j] = (i == j ? 0 : -1e9);
	}
	Maxtir operator * (const Maxtir &a) const {
		Maxtir c;
		c.init();
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j)
				for (int k = 1; k <= n; ++k)
					c[i][j] = std::max(c[i][j], m[i][k] + a[k][j]);
		return c;
	}
	bool ok() {
		for (int i = 1; i <= n; ++i) if (m[i][i] > 0) return true;
		return false;
	}
} r, tp, f[10];
signed main() {
	n = rd();
	int m = rd();
	f[0].init();
	rep(i, 1, m) {
		int u = rd(), v = rd();
		f[0][u][v] = rd(), f[0][v][u] = rd();
	}
	for (int x = 1; x <= 9; ++x) f[x] = f[x - 1] * f[x - 1];
	if (!f[9].ok()) return puts("0"), 0;
	int ans = 0;
	r.init();
	for (int i = 8; ~i; --i) {
		tp = r * f[i];
		if (!tp.ok()) ans |= (1 << i), r = tp;
	}
	cout << ans + 1;
	return 0;
}