#include <bits/stdc++.h>
using namespace std;
inline int read() {
  char c;
  int x = 0;
  int b = 1;
  do {
    c = getchar();
    if (c == 45) b = -1;
  } while (c > 57 || c < 48);
  do x = x * 10 + c - 48, c = getchar();
  while (c <= 57 && c >= 48);
  x *= b;
  return x;
}
int n, m, t;
const int maxn = 300 + 5;
const int logn = 10 + 5;
int f[logn][maxn][maxn];
int g[maxn][maxn], w[maxn][maxn];
int main() {
  n = read(), m = read();
  t = log2(n);
  memset(f, 0xcf, sizeof(f));
  memset(w, 0xcf, sizeof(w));
  for (int i = 1, x, y, z, l; i <= m; i++) {
    x = read(), y = read();
    z = read();
    l = read();
    f[0][x][y] = z, f[0][y][x] = l;
  }
  for (int i = 1; i <= n; i++) w[i][i] = f[0][i][i] = 0;
  for (int s = 1; s <= 10; s++) {
    for (int k = 1; k <= n; k++) {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          f[s][i][j] = max(f[s][i][j], f[s - 1][i][k] + f[s - 1][k][j]);
        }
      }
    }
  }
  int ans = 0;
  for (int s = 10; s >= 0; s--) {
    memset(g, 0xcf, sizeof(g));
    for (int k = 1; k <= n; k++) {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          g[i][j] = max(g[i][j], w[i][k] + f[s][k][j]);
        }
      }
    }
    int sig = 0;
    for (int i = 1; i <= n; i++)
      if (g[i][i] > 0) sig = 1;
    if (sig)
      continue;
    else {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          w[i][j] = g[i][j];
        }
      }
      ans += (1 << s);
    }
  }
  printf("%d\n", ans >= n ? 0 : ans + 1);
  return 0;
}
