#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
int f[10][310][310], ans[2][310][310], n;
bool ok(int x) {
  int k, now = 0, i, j, p;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) ans[0][i][j] = i == j ? 0 : -oo;
  for (k = 0; (1 << k) <= x; k++)
    if (x & (1 << k)) {
      now ^= 1;
      for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++) ans[now][i][j] = -oo;
      for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
          for (p = 1; p <= n; p++)
            ans[now][i][j] =
                max(ans[now][i][j], ans[now ^ 1][i][p] + f[k][p][j]);
    }
  for (i = 1; i <= n; i++)
    if (ans[now][i][i] > 0) return 1;
  return 0;
}
int main() {
  int i, j, k, m, p, q, x, y, z, w, l, r, mid;
  scanf("%d%d", &n, &m);
  for (k = 0; (1 << k) <= n; k++)
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++) f[k][i][j] = i == j ? 0 : -oo;
  for (i = 1; i <= m; i++) {
    scanf("%d%d%d%d", &x, &y, &z, &w);
    f[0][x][y] = z;
    f[0][y][x] = w;
  }
  for (k = 1; (1 << k) <= n; k++)
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
        for (x = 1; x <= n; x++)
          f[k][i][j] = max(f[k][i][j], f[k - 1][i][x] + f[k - 1][x][j]);
  l = 2;
  r = n + 1;
  while (l < r) {
    mid = (l + r) / 2;
    if (ok(mid))
      r = mid;
    else
      l = mid + 1;
  }
  printf("%d\n", l % (n + 1));
}
