#include <bits/stdc++.h>
using namespace std;
int N;
vector<vector<int> > mul(vector<vector<int> > &A, vector<vector<int> > &B) {
  vector<vector<int> > res(N, vector<int>(N, (1 << 29)));
  for (int(i) = 0; (i) < (N); (i)++)
    for (int(j) = 0; (j) < (N); (j)++)
      for (int(k) = 0; (k) < (N); (k)++)
        res[i][k] = min(res[i][k], A[i][j] + B[j][k]);
  return res;
}
int M, A, B, C, D;
vector<vector<int> > F[9];
int main() {
  scanf("%d%d", &N, &M);
  F[0] = vector<vector<int> >(N, vector<int>(N, (1 << 29)));
  for (int(i) = 0; (i) < (N); (i)++) F[0][i][i] = 0;
  while (M--) {
    scanf("%d%d%d%d", &A, &B, &C, &D);
    A--, B--;
    F[0][A][B] = -C, F[0][B][A] = -D;
  }
  for (int(i) = (1); (i) < (9); (i)++) F[i] = mul(F[i - 1], F[i - 1]);
  vector<vector<int> > T(N, vector<int>(N, (1 << 29)));
  for (int(i) = 0; (i) < (N); (i)++) T[i][i] = 0;
  int res = 0;
  for (int c = 8; c >= 0; c--) {
    vector<vector<int> > tmp = mul(T, F[c]);
    bool ok = false;
    for (int(i) = 0; (i) < (N); (i)++)
      if (tmp[i][i] < 0) ok = true;
    if (!ok) {
      T = tmp;
      res += (1 << c);
    }
  }
  if (res > N)
    puts("0");
  else
    printf("%d\n", ++res);
}
