#include <bits/stdc++.h>
using namespace std;
const int N = 3e2 + 5, INF = 0x3f3f3f3f;
int n, m;
int f[N][N][N], dp[N][N][N];
int ans;
int main() {
  scanf("%d%d", &n, &m);
  memset(f, 0xcf, sizeof(f));
  memset(dp, 0xcf, sizeof(f));
  for (int i = 1; i <= n; ++i) f[0][i][i] = 0;
  for (int i = 1; i <= m; ++i) {
    int x, y, a, b;
    scanf("%d%d%d%d", &x, &y, &a, &b);
    f[0][x][y] = dp[1][x][y] = a;
    f[0][y][x] = dp[1][y][x] = b;
  }
  for (int p = 1; p <= 9; ++p)
    for (int k = 1; k <= n; ++k)
      for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
          f[p][i][j] = max(f[p][i][j], f[p - 1][i][k] + f[p - 1][k][j]);
  for (int i = 1; i <= n; ++i)
    if (f[9][i][i] > 0) ans = 1;
  if (!ans) {
    printf("0");
    return 0;
  }
  for (int q = 9; q >= 0; --q) {
    ans += (1 << q);
    memset(dp[ans], 0xcf, sizeof(dp[ans]));
    for (int k = 1; k <= n; ++k)
      for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
          dp[ans][i][j] =
              max(dp[ans][i][j], dp[ans - (1 << q)][i][k] + f[q][k][j]);
    for (int i = 1; i <= n; ++i)
      if (dp[ans][i][i] > 0) i += n, ans -= (1 << q);
  }
  printf("%d\n", ++ans);
  return 0;
}
