#include <bits/stdc++.h>
using namespace std;
struct Matrix {
  int ele[320][320];
};
int n, m;
Matrix orig, dp[16], tmp, tmp2, res;
Matrix operator*(const Matrix &a, const Matrix &b) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      res.ele[i][j] = i == j ? 0 : -0x3FFFFFFF;
      for (int k = 0; k < n; k++) {
        if (a.ele[i][k] != -0x3FFFFFFF && b.ele[k][j] != -0x3FFFFFFF) {
          res.ele[i][j] = max(res.ele[i][j], a.ele[i][k] + b.ele[k][j]);
        }
      }
    }
  }
  return res;
}
int my_log2(int num) {
  int ans = 0;
  while (num) {
    ans++;
    num >>= 1;
  }
  return ans - 1;
}
bool test(const Matrix &a) {
  for (int i = 0; i < n; i++) {
    if (a.ele[i][i] > 0) return true;
  }
  return false;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      orig.ele[i][j] = i == j ? 0 : -0x3FFFFFFF;
    }
  }
  for (int i = 0; i < m; i++) {
    int a, b, x, y;
    cin >> a >> b >> x >> y;
    orig.ele[--a][--b] = x;
    orig.ele[b][a] = y;
  }
  dp[0] = orig;
  for (int i = 1; (1 << i) <= n; i++) dp[i] = dp[i - 1] * dp[i - 1];
  tmp = orig;
  int ans = 1;
  for (int i = my_log2(n); i >= 0; i--) {
    tmp2 = tmp * dp[i];
    if (!test(tmp2)) {
      tmp = tmp2;
      ans += 1 << i;
    }
  }
  tmp = tmp * orig;
  if (test(tmp))
    cout << ++ans << endl;
  else
    cout << 0 << endl;
  return 0;
}
