#include <bits/stdc++.h>
using namespace std;
const int MAXN = 350;
int n, m;
int dis[MAXN][MAXN][25];
int ans[MAXN][MAXN];
int now[MAXN][MAXN];
int INF = 1 << 30;
int read() {
  int f = 1, x = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x *= 10;
    x += ch - '0';
    ch = getchar();
  }
  return x * f;
}
int main() {
  memset(now, 0xcf, sizeof(now));
  memset(dis, 0xcf, sizeof(dis));
  n = read();
  m = read();
  for (int i = 1; i <= m; i++) {
    int x, y, z, w;
    x = read();
    y = read();
    z = read();
    w = read();
    dis[x][y][0] = z;
    dis[y][x][0] = w;
  }
  for (int i = 1; i <= n; i++) {
    now[i][i] = 0;
    dis[i][i][0] = 0;
  }
  for (int s = 1; s <= 10; s++) {
    for (int k = 1; k <= n; k++) {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          dis[i][j][s] = max(dis[i][j][s], dis[i][k][s - 1] + dis[k][j][s - 1]);
        }
      }
    }
  }
  int res = 0;
  for (int s = 10; s >= 0; s--) {
    memset(ans, 0xcf, sizeof(ans));
    for (int k = 1; k <= n; k++) {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          ans[i][j] = max(ans[i][j], now[i][k] + dis[k][j][s]);
        }
      }
    }
    bool f = 0;
    for (int i = 1; i <= n; i++) {
      if (ans[i][i] > 0) {
        f = 1;
        break;
      }
    }
    if (f)
      continue;
    else {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          now[i][j] = ans[i][j];
        }
      }
      res += (1 << s);
    }
  }
  cout << (res >= n ? 0 : res + 1) << endl;
  return 0;
}
