#include <bits/stdc++.h>
using namespace std;
inline int in() {
  int32_t x;
  scanf("%d", &x);
  return x;
}
inline long long lin() {
  long long x;
  scanf("%lld", &x);
  return x;
}
const int maxn = 300 + 10;
const int inf = 1e9 + 10;
int n, m;
struct matrix {
  int a[maxn][maxn];
  matrix() {
    for (int i = 0; i < maxn; i++)
      for (int j = 0; j < maxn; j++) a[i][j] = i == j ? 0 : -inf;
  }
  inline int *operator[](const int &x) { return a[x]; }
} mat[9];
inline matrix operator*(matrix &a, matrix &b) {
  matrix ret;
  for (int i = 0; i < n; i++)
    for (int k = 0; k < n; k++)
      for (int j = 0; j < n; j++) ret[i][j] = max(ret[i][j], a[i][k] + b[k][j]);
  return ret;
}
int ans;
int32_t main() {
  n = in(), m = in();
  for (int i = 0; i < m; i++) {
    int v = in() - 1, u = in() - 1;
    mat[0][v][u] = in(), mat[0][u][v] = in();
  }
  for (int i = 1; i < 9; i++) mat[i] = mat[i - 1] * mat[i - 1];
  matrix cur;
  for (int i = 8; i >= 0; i--) {
    matrix shit = cur * mat[i];
    bool fl = false;
    for (int node = 0; node < n && !fl; node++)
      if (shit[node][node] > 0) fl = true;
    if (!fl) ans += (1 << i), cur = shit;
  }
  if (ans == (1 << 9) - 1) return cout << 0 << endl, 0;
  cout << ans + 1 << endl;
}
