#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
int n, m, ans = 1;
inline int mymax(const int& a, const int& b) { return a > b ? a : b; }
inline int getlog(int _) {
  int ret = 0;
  while (_) {
    ret++;
    _ >>= 1;
  }
  return ret - 1;
}
struct mat {
  int num[333][333];
  inline mat times(const mat& b) {
    mat res;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) {
        res.num[i][j] = i == j ? 0 : -INF;
        for (int k = 0; k < n; k++)
          if (num[i][k] != -INF && b.num[k][j] != -INF)
            res.num[i][j] = mymax(res.num[i][j], num[i][k] + b.num[k][j]);
      }
    return res;
  }
} g, f[10], t;
void init() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) g.num[i][j] = i == j ? 0 : -INF;
  while (m--) {
    int i, j, x, y;
    scanf("%d%d%d%d", &i, &j, &x, &y);
    i--;
    j--;
    g.num[i][j] = x;
    g.num[j][i] = y;
  }
  f[0] = g;
  for (int i = 1; (1 << i) <= n; i++) f[i] = f[i - 1].times(f[i - 1]);
  return;
}
inline bool check(const mat& _) {
  for (int i = 0; i < n; i++)
    if (_.num[i][i] > 0) return 1;
  return 0;
}
void slove() {
  t = g;
  for (int i = getlog(n); i >= 0; i--) {
    mat T;
    T = t.times(f[i]);
    if (!check(T)) {
      t = T;
      ans += 1 << i;
    }
  }
  t = t.times(g);
  printf("%d\n", check(t) ? ans + 1 : 0);
  return;
}
int main() {
  init();
  slove();
  return 0;
}
