#include <bits/stdc++.h>
const int N = 310, P = INT_MIN / 10;
int w[10][N][N], s[N][N], t[N][N];
int main() {
  int n, m, i, j, k, l, x, y, s1, s2, ans = 1, max, sum[10];
  bool p;
  scanf("%d %d", &n, &m);
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) w[0][i][j] = P;
  for (i = 1; i <= m; i++) {
    scanf("%d %d %d %d", &x, &y, &s1, &s2);
    w[0][x][y] = s1;
    w[0][y][x] = s2;
  }
  for (i = 1; i <= n; i++) w[0][i][i] = 0;
  sum[0] = 1;
  i = 0;
  while (sum[i] * 2 <= n) {
    sum[i + 1] = sum[i] * 2;
    for (j = 1; j <= n; j++)
      for (k = 1; k <= n; k++) w[i + 1][j][k] = P;
    for (l = 1; l <= n; l++)
      for (j = 1; j <= n; j++)
        for (k = 1; k <= n; k++)
          if (w[i + 1][j][k] < w[i][j][l] + w[i][l][k])
            w[i + 1][j][k] = w[i][j][l] + w[i][l][k];
    i++;
  }
  max = i;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) s[i][j] = P;
  for (i = 1; i <= n; i++) s[i][i] = 0;
  for (i = max; i >= 0; i--) {
    for (j = 1; j <= n; j++)
      for (k = 1; k <= n; k++) t[j][k] = P;
    for (l = 1; l <= n; l++)
      for (j = 1; j <= n; j++)
        for (k = 1; k <= n; k++) {
          if (t[j][k] < s[j][l] + w[i][l][k]) t[j][k] = s[j][l] + w[i][l][k];
          if (t[j][k] < w[i][j][l] + s[l][k]) t[j][k] = w[i][j][l] + s[l][k];
        }
    p = false;
    for (j = 1; j <= n; j++)
      if (t[j][j] > 0) {
        p = true;
        break;
      }
    if (!p) {
      ans += sum[i];
      memcpy(s, t, sizeof(t));
    }
  }
  if (ans <= n)
    printf("%d", ans);
  else
    printf("0");
  return (0);
}
