#include <bits/stdc++.h>
using namespace std;
const int N = 320;
int g[10][320][320], f[320][320], s[320][320];
int n, m;
int main() {
  int x, y, z, w;
  scanf("%d%d", &n, &m);
  for (int i = 0; i <= 9; i++)
    for (int j = 1; j <= n; j++)
      for (int k = 1; k <= n; k++) g[i][j][k] = -1e9;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) f[i][j] = -1e9;
  for (int i = 1; i <= n; i++) f[i][i] = g[0][i][i] = 0;
  for (int i = 1; i <= m; i++)
    scanf("%d%d%d%d", &x, &y, &z, &w), g[0][x][y] = z, g[0][y][x] = w;
  for (int l = 1; l <= 9; l++)
    for (int k = 1; k <= n; k++)
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
          g[l][i][j] = max(g[l][i][j], g[l - 1][i][k] + g[l - 1][k][j]);
  int ans = 0;
  for (int l = 9; l >= 0; l--) {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) s[i][j] = f[i][j];
    for (int k = 1; k <= n; k++)
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
          s[i][j] = max(f[i][k] + g[l][k][j], s[i][j]);
    bool flag = false;
    for (int i = 1; i <= n; i++)
      if (s[i][i] > 0) {
        flag = true;
        break;
      }
    if (flag) continue;
    ans += 1 << l;
    if (ans > n) {
      puts("0");
      return 0;
    }
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) f[i][j] = s[i][j];
  }
  printf("%d", ans + 1);
  return 0;
}
