#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1, c = getchar();
  while (c < 48) c == '-' && (f = -1), c = getchar();
  while (c > 47) x = x * 10 + c - '0', c = getchar();
  return x * f;
}
const int MAXN = 305;
int n, m;
struct Matrix {
  int s[MAXN][MAXN];
  int *operator[](int i) { return s[i]; }
  inline void init() { memset(s, 0xc0, sizeof(s)); }
} mat[15], now, nxt;
Matrix operator*(Matrix a, Matrix b) {
  Matrix res;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      res[i][j] = max(a[i][j], b[i][j]);
      for (int k = 1; k <= n; ++k)
        res[i][j] = max(res[i][j], a[i][k] + b[k][j]);
    }
  return res;
}
int main(int argc, char const *argv[]) {
  n = read();
  m = read();
  now.init(), mat[0].init();
  for (int i = 1; i <= n; ++i) now[i][i] = 0;
  for (int i = 1; i <= m; ++i) {
    int u = read(), v = read();
    mat[0][u][v] = read(), mat[0][v][u] = read();
  }
  for (int i = 1; i <= 9; ++i) mat[i] = mat[i - 1] * mat[i - 1];
  int ans = 0;
  for (int i = 9; ~i; --i) {
    int flag = 0;
    nxt = now * mat[i];
    for (int j = 1; j <= n; ++j)
      if (nxt[j][j] > 0) {
        flag = 1;
        break;
      }
    if (flag) continue;
    now = nxt, ans += (1 << i);
  }
  printf("%d\n", ans > n ? 0 : ans + 1);
  return 0;
}
