#include <bits/stdc++.h>
using namespace std;
const int maxn = 310, inf = 1 << 30;
int n, m, f[25][maxn][maxn], ans[2][maxn][maxn];
bool check(int x) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) ans[0][i][j] = -inf;
    ans[0][i][i] = 0;
  }
  int now = 0;
  for (int t = 0; t <= 20; t++) {
    if (!((1 << t) & x)) continue;
    now ^= 1;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) ans[now][i][j] = -inf;
      ans[now][i][i] = 0;
    }
    for (int k = 1; k <= n; k++) {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
          ans[now][i][j] = max(ans[now][i][j], ans[now ^ 1][i][k] + f[t][j][k]);
      }
    }
  }
  for (int i = 1; i <= n; i++)
    if (ans[now][i][i] > 0) return true;
  return false;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int t = 0; t <= 20; t++) {
    for (int i = 0; i < maxn; i++) {
      for (int j = 0; j < maxn; j++) f[t][i][j] = -inf;
      f[t][i][i] = 0;
    }
  }
  for (int i = 1, x, y; i <= m; i++) {
    scanf("%d%d", &x, &y);
    scanf("%d%d", &f[0][x][y], &f[0][y][x]);
  }
  for (int t = 1; t <= 20; t++) {
    for (int k = 1; k <= n; k++) {
      for (int i = 1; i <= n; i++) {
        if (f[t - 1][i][k] == -inf) continue;
        for (int j = 1; j <= n; j++)
          f[t][i][j] = max(f[t][i][j], f[t - 1][i][k] + f[t - 1][k][j]);
      }
    }
  }
  int l = 2, r = n + 1, ans = 0;
  while (l <= r) {
    int mid = l + r >> 1;
    if (check(mid))
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  if (ans >= n + 1) ans = 0;
  printf("%d\n", ans);
  return 0;
}
