#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
const int maxint = 1 << 30;
struct matrix {
  int data[maxn][maxn];
};
int g[maxn][maxn];
int n, m;
matrix operator*(const matrix &a, const matrix &b) {
  matrix c;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      c.data[i][j] = -maxint;
      for (int k = 1; k <= n; k++)
        c.data[i][j] = max(c.data[i][j], a.data[i][k] + b.data[k][j]);
    }
  }
  return c;
}
bool judge(int mid) {
  matrix a;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) a.data[i][j] = g[i][j];
  matrix ans;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) ans.data[i][j] = (i == j) ? 0 : -maxint;
  while (mid > 0) {
    if (mid & 1) ans = ans * a;
    mid /= 2;
    a = a * a;
  }
  for (int i = 1; i <= n; i++)
    if (ans.data[i][i] > 0) return true;
  return false;
}
int main() {
  int a, b, c, d;
  while (scanf("%d%d", &n, &m) != EOF) {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) g[i][j] = (i == j) ? 0 : -maxint;
    while (m--) {
      scanf("%d%d%d%d", &a, &b, &c, &d);
      g[a][b] = c;
      g[b][a] = d;
    }
    int l = 2, r = n + 5, ans = 0;
    while (l <= r) {
      int mid = (l + r) / 2;
      if (judge(mid)) {
        ans = mid;
        r = mid - 1;
      } else
        l = mid + 1;
    }
    cout << ans << endl;
  }
  return 0;
}
