#include <bits/stdc++.h>
int n, m, x, y, tmp, ans;
struct mat {
  int v[305][305];
} g[9], p, q;
mat operator*(mat a, mat b) {
  mat res;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      res.v[i][j] = a.v[i][j];
      if (b.v[i][j] < res.v[i][j]) res.v[i][j] = b.v[i][j];
      for (int k = 1; k <= n; k++)
        if (a.v[i][k] + b.v[k][j] > res.v[i][j])
          res.v[i][j] = a.v[i][k] + b.v[k][j];
    }
  return res;
}
void clear(mat& a) {
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) a.v[i][j] = i == j ? 0 : -1 << 22;
}
bool check(mat a) {
  for (int i = 1; i <= n; i++)
    if (a.v[i][i] > 0) return true;
  return false;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) g[0].v[i][j] = -1 << 22;
  while (m--) {
    scanf("%d%d", &x, &y);
    scanf("%d%d", &g[0].v[x][y], &g[0].v[y][x]);
  }
  for (int t = 1; t <= 8; t++) g[t] = g[t - 1] * g[t - 1];
  clear(p);
  tmp = 0;
  ans = 0;
  for (int i = 8; i >= 0; i--) {
    q = p * g[i];
    if (check(q))
      ans = tmp + (1 << i);
    else
      tmp = tmp + (1 << i), p = q;
  }
  printf("%d", ans);
}
