#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
int N, M;
int F[305][305][12], G[305][305], G2[305][305];
void init() {
  int i, j, l, x, y;
  scanf("%d%d", &N, &M);
  memset(F, 0xF0, sizeof(F));
  for (i = 1; i <= M; i++) {
    scanf("%d%d", &x, &y);
    scanf("%d%d", &F[x][y][0], &F[y][x][0]);
  }
}
inline void MAX(int &a, int b) {
  if (a < b) a = b;
}
void work() {
  int l, i, j, k, ans = 0;
  memset(G, 0xF0, sizeof(G));
  for (i = 1; i <= N; i++) G[i][i] = F[i][i][0] = 0;
  for (l = 1; l <= 8; l++)
    for (k = 1; k <= N; k++)
      for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
          MAX(F[i][j][l], F[i][k][l - 1] + F[k][j][l - 1]);
  for (l = 8; l >= 0; l--) {
    memset(G2, 0xF0, sizeof(G2));
    for (k = 1; k <= N; k++) {
      for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++) MAX(G2[i][j], G[i][k] + F[k][j][l]);
    }
    for (i = 1; i <= N; i++)
      if (G2[i][i] > 0) break;
    if (i <= N) continue;
    memcpy(G, G2, sizeof(G));
    ans += 1 << l;
  }
  cout << (ans >= N ? 0 : ans + 1) << endl;
}
int main() {
  init();
  work();
  return 0;
}
