#include <bits/stdc++.h>
const int maxn = 305, maxk = 11;
int n, m, tot;
struct matrix {
  int len, wid;
  int mt[maxn][maxn];
} st, zero, tmp, now, ans[maxk];
inline int max(int a, int b) { return a > b ? a : b; }
matrix mul(matrix a, matrix b) {
  matrix res = zero;
  res.len = a.len, res.wid = b.wid;
  for (int i = 1; i <= a.len; i++)
    for (int j = 1; j <= b.wid; j++)
      for (int k = 1; k <= a.wid; k++)
        res.mt[i][j] = max(res.mt[i][j], a.mt[i][k] + b.mt[k][j]);
  return res;
}
int main() {
  scanf("%d%d", &n, &m);
  zero.len = zero.wid = 0;
  for (int i = 0; i < maxn; i++)
    for (int j = 0; j < maxn; j++) zero.mt[i][j] = -1000000000;
  st = zero;
  st.len = st.wid = n;
  for (int i = 1; i <= n; i++) st.mt[i][i] = 0;
  for (int i = 1; i <= m; i++) {
    int x, y, a, b;
    scanf("%d%d%d%d", &x, &y, &a, &b);
    st.mt[x][y] = a, st.mt[y][x] = b;
  }
  ans[0] = st;
  for (int i = 1; i <= 10; i++) ans[i] = mul(ans[i - 1], ans[i - 1]);
  now = zero;
  now.len = now.wid = n;
  for (int i = 1; i <= n; i++) now.mt[i][i] = 0;
  for (int i = 10; i >= 0; i--) {
    int flg = 1;
    tmp = mul(now, ans[i]);
    for (int j = 1; j <= n; j++)
      if (tmp.mt[j][j] > 0) {
        flg = 0;
        break;
      }
    if (flg == 0) continue;
    tot += (1 << i);
    now = tmp;
  }
  printf("%d\n", tot >= n ? 0 : tot + 1);
  return 0;
}
