#include <bits/stdc++.h>
using namespace std;
template <class Z>
inline bool checkmax(Z &a, Z b) {
  if (a == -1 || a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class Z>
inline bool checkmin(Z &a, Z b) {
  if (a == -1 || a > b) {
    a = b;
    return true;
  }
  return false;
}
int mod = 1000000007;
struct Matrix {
  int num[310][310];
  int n, m;
  Matrix() {
    for (int i = 0; i < 310; i++) {
      for (int j = 0; j < 310; j++) {
        num[i][j] = -99999999;
      }
    }
  }
  Matrix(int _n, int _m) {
    n = _n;
    m = _m;
    for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= m; j++) {
        num[i][j] = -99999999;
      }
    }
  }
  Matrix operator+(const Matrix &B) const {
    Matrix C(n, m);
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        C.num[i][j] = num[i][j] + B.num[i][j];
        if (C.num[i][j] >= mod) C.num[i][j] %= mod;
      }
    }
    return C;
  }
  Matrix operator*(const Matrix &B) const {
    Matrix C(n, B.m);
    for (int i = 1; i <= n; i++) {
      for (int k = 1; k <= m; k++) {
        for (int j = 1; j <= B.m; j++) {
          C.num[i][j] = max(C.num[i][j], num[i][k] + B.num[k][j]);
        }
      }
    }
    return C;
  }
  friend Matrix operator^(const Matrix &A, const int &k) {
    int kk = k;
    Matrix tp = A;
    Matrix C(A.n, A.m);
    for (int i = 1; i <= C.n; i++) C.num[i][i] = 0;
    while (kk > 0) {
      if (kk & 1) C = C * tp;
      tp = tp * tp;
      kk >>= 1;
    }
    return C;
  }
  void show() {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        printf("%d", num[i][j]);
        if (j == m)
          printf("\n");
        else
          printf(" ");
      }
    }
  }
} I;
Matrix Sum(Matrix A, int k) {
  if (k == 1)
    return A;
  else if (k & 1)
    return Sum(A, k - 1) + (A ^ k);
  else
    return Sum(A, k >> 1) * ((A ^ (k >> 1)) + I);
}
void initI(int n) {
  I.n = I.n = n;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      I.num[i][j] = (i == j);
    }
  }
}
Matrix save[10];
int main() {
  int i, j;
  int n, m;
  int a, b, c1, c2;
  while (scanf("%d%d", &n, &m) != EOF) {
    Matrix res(n, n);
    for (i = 1; i <= n; i++) res.num[i][i] = 0;
    Matrix temp = res;
    for (i = 1; i <= m; i++) {
      scanf("%d%d%d%d", &a, &b, &c1, &c2);
      res.num[a][b] = c1;
      res.num[b][a] = c2;
    }
    save[0] = res;
    for (i = 1; i < 10; i++) {
      save[i] = save[i - 1] * save[i - 1];
    }
    int ff = 0;
    for (i = 1; i <= n; i++) {
      if (save[9].num[i][i] > 0) ff = 1;
    }
    if (!ff) {
      puts("0");
      continue;
    }
    int ans = 0;
    for (i = 9; i >= 0; i--) {
      ff = 0;
      Matrix tt = temp * save[i];
      for (j = 1; j <= n; j++) {
        if (tt.num[j][j] > 0) ff = 1;
      }
      if (!ff) {
        temp = tt;
        ans += (1 << (i));
      }
    }
    printf("%d\n", ans + 1);
  }
  return 0;
}
