#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int MAXN = 305;
int graph[MAXN][MAXN];
int n, m;
struct mat {
  int a[MAXN][MAXN];
  mat() {
    for (int i = 1; i <= 300; i++)
      for (int j = 1; j <= 300; j++) a[i][j] = -(int)1e9;
    for (int i = 1; i <= 300; i++) a[i][i] = 0;
  }
  mat operator*(mat b) const {
    mat r;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        for (int k = 1; k <= n; k++)
          r.a[i][j] = max(r.a[i][j], a[i][k] + b.a[k][j]);
    return r;
  }
} base[15];
mat power(mat x, int n) {
  n--;
  mat res = x;
  while (n) {
    if (n & 1) res = res * x;
    x = x * x;
    n >>= 1;
  }
  return res;
}
bool chk(mat &res) {
  for (int i = 1; i <= n; i++)
    if (res.a[i][i] > 0) return true;
  return false;
}
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, uv, vu;
    cin >> u >> v >> uv >> vu;
    base[0].a[u][v] = uv;
    base[0].a[v][u] = vu;
  }
  for (int i = 1; i <= 9; i++) base[i] = base[i - 1] * base[i - 1];
  if (!chk(base[9])) return cout << 0, 0;
  mat res;
  int ans = 0;
  for (int i = 8; i >= 0; i--) {
    mat pp = res * base[i];
    if (!chk(pp)) {
      res = pp;
      ans += (1 << i);
    }
  }
  cout << ans + 1;
}
