#include <bits/stdc++.h>
using namespace std;
const long long INF = -100000000000LL;
struct Matrix {
  int r, c;
  vector<vector<long long> > mat;
  Matrix(int rr, int cc)
      : r(rr),
        c(cc),
        mat(vector<vector<long long> >(r, vector<long long>(c, 0))) {}
  Matrix(vector<vector<long long> > vec)
      : r(vec.size()), c(vec[0].size()), mat(vec) {}
  Matrix identity(int n) {
    Matrix I(n, n);
    for (int i = 0; i < n; i++) I.mat[i][i] = 1;
    return I;
  }
  bool awesome() {
    for (int i = 0; i < r; i++)
      if (mat[i][i] > 0) return true;
    return false;
  }
  Matrix operator*(Matrix M) {
    if (c != M.r) {
      cout << "Not multiplicable\n" << endl;
      exit(0);
    }
    Matrix res(M.r, M.c);
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < M.c; j++) {
        long long mcost = INF;
        for (int k = 0; k < c; k++) {
          mcost = max(mcost, mat[i][k] + M.mat[k][j]);
        }
        res.mat[i][j] = mcost;
      }
    }
    return res;
  }
  Matrix operator^(int n) {
    Matrix A = *this, B = identity(r);
    while (n) {
      if (n & 1) B = B * A;
      A = A * A;
      n >>= 1;
    }
    return B;
  }
  void _print() {
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) printf("%I64d ", mat[i][j]);
      printf("\n");
    }
    return;
  }
};
int main() {
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  Matrix cost(n, n);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (i != j) cost.mat[i][j] = INF;
  Matrix cur(cost);
  for (int i = 0; i < m; i++) {
    int u, v, x, y;
    cin >> u >> v >> x >> y;
    --u;
    --v;
    cost.mat[u][v] = x;
    cost.mat[v][u] = y;
  }
  vector<Matrix> edges_2_k(10, Matrix(n, n));
  edges_2_k[0] = cost;
  for (int i = 1; i < 10; i++) {
    edges_2_k[i] = edges_2_k[i - 1] * edges_2_k[i - 1];
  }
  if (!edges_2_k[9].awesome()) {
    cout << "0" << endl;
    return 0;
  }
  int ans = 1;
  for (int i = 8; i >= 0; i--) {
    Matrix new_cur = cur * edges_2_k[i];
    if (!new_cur.awesome()) {
      ans += (1 << i);
      cur = new_cur;
    }
  }
  cout << ans << endl;
  return 0;
}
