#include <bits/stdc++.h>
using namespace std;
const int N = 302;
int d[20][N][N], la[N][N], tmp[N][N];
int l, ans, n, m;
void matcpy(int a[N][N], const int b[N][N]) {
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) a[i][j] = b[i][j];
}
void mul(int c[N][N], const int a[N][N], const int b[N][N]) {
  int i, j, k;
  for (i = 1; i <= n; ++i) fill(c[i] + 1, c[i] + n + 1, -(1 << 25));
  for (k = 1; k <= n; ++k)
    for (i = 1; i <= n; ++i)
      for (j = 1; j <= n; ++j) c[i][j] = max(c[i][j], a[i][k] + b[k][j]);
}
bool check(const int a[N][N]) {
  for (int i = 1; i <= n; ++i)
    if (a[i][i] > 0) return 1;
  matcpy(la, a);
  return 0;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) fill(d[0][i] + 1, d[0][i] + n + 1, -(1 << 25));
  for (int s, t, x, y, i = 1; i <= m; ++i) {
    scanf("%d%d%d%d", &s, &t, &x, &y);
    d[0][s][t] = max(d[0][s][t], x);
    d[0][t][s] = max(d[0][t][s], y);
  }
  for (int i = 1; i <= n; ++i) d[0][i][i] = 0;
  matcpy(tmp, d[0]);
  for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        tmp[i][j] = max(tmp[i][j], tmp[i][k] + tmp[k][j]);
  if (!check(tmp)) {
    printf("0\n");
    return 0;
  }
  matcpy(la, d[0]);
  l = 0;
  for (int i = 1;; ++i) {
    mul(d[i], d[i - 1], d[i - 1]);
    if (check(d[i]))
      break;
    else
      l = i;
  }
  ans = (1 << l);
  for (int j = l - 1; j >= 0; --j) {
    mul(tmp, la, d[j]);
    if (!check(tmp)) ans += (1 << j);
  }
  printf("%d\n", ans + 1);
  return 0;
}
