#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
long long read() {
  long long x = 0;
  long long f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -f;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= f;
  return x;
}
long long n, m;
struct matrix {
  long long s[315][315];
  void inti() {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) s[i][j] = -0x3f3f3f3f;
    return;
  }
  matrix operator*(matrix b) const {
    matrix f;
    f.inti();
    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], s[i][k] + b.s[k][j]);
    return f;
  }
} t[10], now, p;
int main() {
  n = read(), m = read();
  t[0].inti();
  for (int i = 1; i <= n; i++) t[0].s[i][i] = 0;
  for (int i = 1; i <= m; i++) {
    long long u = read(), v = read();
    t[0].s[u][v] = read();
    t[0].s[v][u] = read();
  }
  for (int i = 1; i < 10; i++) t[i] = t[i - 1] * t[i - 1];
  now.inti(), p.inti();
  for (int i = 1; i <= n; i++) now.s[i][i] = 0;
  long long ans = 0;
  for (int i = 10 - 1; ~i; i--) {
    p = now * t[i];
    bool flag = 0;
    for (int j = 1; j <= n; j++)
      if (p.s[j][j] > 0) {
        flag = 1;
        break;
      }
    if (flag) continue;
    ans += (1 << i), now = p;
  }
  if (ans > n)
    puts("0");
  else
    printf("%lld", ans + 1);
}
