#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD7 = (int)1e9 + 7;
template <class T1, class T2>
int upmin(T1 &x, T2 v) {
  if (x > v) {
    x = v;
    return 1;
  }
  return 0;
}
template <class T1, class T2>
int upmax(T1 &x, T2 v) {
  if (x < v) {
    x = v;
    return 1;
  }
  return 0;
}
int N, M;
vector<tuple<int, int, int, int> > C;
void init() {
  cin >> N >> M;
  C = vector<tuple<int, int, int, int> >(M);
  for (int i = 0; i < M; ++i) {
    int x, y, cxy, cyx;
    cin >> x >> y >> cxy >> cyx;
    C[i] = make_tuple(x - 1, y - 1, cxy, cyx);
  }
}
int maxp;
vector<vector<vector<int> > > dbl;
vector<vector<vector<int> > > pdbl;
vector<vector<int> > I;
vector<vector<int> > mat_mul(vector<vector<int> > a, vector<vector<int> > b) {
  vector<vector<int> > res = I;
  for (int i = 0; i < a.size(); ++i)
    for (int j = 0; j < b.size(); ++j)
      for (int k = 0; k < b[0].size(); ++k) upmax(res[i][k], a[i][j] + b[j][k]);
  return res;
}
void preprocess() {
  I = vector<vector<int> >(N, vector<int>(N, -INF));
  for (int i = 0; i < N; ++i) I[i][i] = 0;
  maxp = 32 - __builtin_clz(N) - 1;
  dbl = pdbl = vector<vector<vector<int> > >(
      maxp + 1, vector<vector<int> >(N, vector<int>(N)));
  dbl[0] = I;
  for (int i = 0; i < M; ++i) {
    int x, y, cxy, cyx;
    tie(x, y, cxy, cyx) = C[i];
    dbl[0][x][y] = cxy;
    dbl[0][y][x] = cyx;
  }
  for (int i = 0; i < maxp; ++i) dbl[i + 1] = mat_mul(dbl[i], dbl[i]);
  pdbl[0] = I;
  for (int i = 0; i < maxp; ++i) pdbl[i + 1] = mat_mul(pdbl[i], dbl[i]);
}
void solve() {
  int ans = 0;
  vector<vector<int> > pre = I;
  for (int i = maxp; 0 <= i; --i) {
    int ok = 0;
    vector<vector<int> > cur = mat_mul(pre, pdbl[i]);
    for (int j = 0; j < N; ++j) ok |= cur[j][j] > 0;
    if (not ok) ans |= 1 << i, pre = mat_mul(pre, dbl[i]);
  }
  int ok = 0;
  for (int i = 0; i < N; ++i) ok |= pre[i][i] > 0;
  if (not ok)
    cout << 0 << endl;
  else
    cout << ans << endl;
}
signed main() {
  ios::sync_with_stdio(0);
  init();
  preprocess();
  solve();
  return 0;
}
