#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int N = 2e5 + 5, INF = 1e9;
const bool debug = 0;
int n, m, a, b, c1, c2;
struct matrix {
  vector<vector<int> > M;
  int n, m;
  matrix() {}
  matrix(int nn, int mm) {
    n = nn;
    m = mm;
    M.resize(n);
    for (int i = 0; i < n; ++i) M[i].resize(m);
  }
  matrix(int nn, int mm, int z) {
    n = nn;
    m = mm;
    M.resize(n);
    for (int i = 0; i < n; ++i) M[i].resize(m);
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j) M[i][j] = z;
  }
  vector<int>& operator[](int x) { return M[x]; }
  const vector<int>& operator[](int x) const { return M[x]; }
};
matrix operator*(const matrix& a, const matrix& b) {
  matrix c(a.n, b.m, -INF);
  for (int i = 0; i < a.n; ++i)
    for (int j = 0; j < b.m; ++j)
      for (int k = 0; k < a.m; ++k)
        if (a[i][k] > -INF && b[k][j] > -INF && c[i][j] < a[i][k] + b[k][j])
          c[i][j] = a[i][k] + b[k][j];
  return c;
}
bool h(const matrix& a) {
  for (int i = 0; i < a.n; ++i)
    if (a[i][i] > 0) return true;
  return false;
}
int main() {
  if (debug) freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  matrix g(n, n, -INF);
  for (int i = 0; i < n; ++i) g[i][i] = 0;
  for (int i = 0; i < m; ++i) {
    cin >> a >> b >> c1 >> c2;
    --a;
    --b;
    g[a][b] = max(g[a][b], c1);
    g[b][a] = max(g[b][a], c2);
  }
  int l = 1, r = n + 1;
  vector<matrix> stpd(10);
  stpd[0] = g;
  for (int i = 1; i < 10; ++i) stpd[i] = stpd[i - 1] * stpd[i - 1];
  for (int k = 9; k >= 0; --k) {
    matrix pg = g * stpd[k];
    if (!h(pg)) {
      l += (1 << k);
      g = pg;
    }
  }
  cout << (l + 1 > n ? 0 : l + 1);
  return 0;
}
