#include <bits/stdc++.h>
int e[9][320][320], r[320][320], t[320][320];
void gt(int& x, int y) {
  if (x < y) x = y;
}
int n, m, i, j, k, a;
int main() {
  memset(e, 0xF0, sizeof(e));
  memset(r, 0xF0, sizeof(r));
  scanf("%d%d", &n, &m);
  for (k = 0; k < m; ++k) {
    scanf("%d%d", &i, &j);
    --i, --j;
    scanf("%d%d", &e[0][i][j], &e[0][j][i]);
  }
  for (i = 0; i < n; ++i) e[0][i][i] = r[i][i] = 0;
  for (m = 0; m < 8; ++m)
    for (k = 0; k < n; ++k)
      for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j) gt(e[m + 1][i][j], e[m][i][k] + e[m][k][j]);
  for (m = 9; m--;) {
    memset(t, 0xF0, sizeof(t));
    for (k = 0; k < n; ++k)
      for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j) gt(t[i][j], r[i][k] + e[m][k][j]);
    for (i = 0; i < n; ++i)
      if (t[i][i] > 0) break;
    if (i == n) {
      a += 1 << m;
      memcpy(r, t, sizeof(t));
    }
  }
  printf("%d\n", a <= n ? a + 1 : 0);
  return 0;
}
