#include <bits/stdc++.h>
using namespace std;
int N;
struct matrix {
  int a[302][302];
};
matrix two[10];
matrix operator*(const matrix &A, const matrix &B) {
  int i, j, k;
  matrix C;
  for ((i) = 0; (i) < (int)(N); (i)++)
    for ((j) = 0; (j) < (int)(N); (j)++)
      C.a[i][j] = ((i == j) ? 0 : -(1 << 29));
  for ((i) = 0; (i) < (int)(N); (i)++)
    for ((j) = 0; (j) < (int)(N); (j)++)
      for ((k) = 0; (k) < (int)(N); (k)++)
        C.a[i][k] = max(C.a[i][k], A.a[i][j] + B.a[j][k]);
  return C;
}
int main(void) {
  int M, i, j, x, y, c1, c2;
  scanf("%d%d", &N, &M);
  matrix A;
  for ((i) = 0; (i) < (int)(N); (i)++)
    for ((j) = 0; (j) < (int)(N); (j)++)
      A.a[i][j] = ((i == j) ? 0 : -(1 << 29));
  for ((i) = 0; (i) < (int)(M); (i)++) {
    scanf("%d%d%d%d", &x, &y, &c1, &c2);
    x--;
    y--;
    A.a[x][y] = c1;
    A.a[y][x] = c2;
  }
  two[0] = A;
  for (i = 1; i <= 8; i++) two[i] = two[i - 1] * two[i - 1];
  matrix B;
  for ((i) = 0; (i) < (int)(N); (i)++)
    for ((j) = 0; (j) < (int)(N); (j)++)
      B.a[i][j] = ((i == j) ? 0 : -(1 << 29));
  int ans = 1;
  for (i = 8; i >= 0; i--) {
    matrix C = B * two[i];
    bool positive = false;
    for ((j) = 0; (j) < (int)(N); (j)++)
      if (C.a[j][j] > 0) positive = true;
    if (!positive) {
      B = C;
      ans += (1 << i);
    }
  }
  if (ans == 512) ans = 0;
  cout << ans << endl;
  return 0;
}
