#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300 + 5;
const int MBIT = 15 + 5;
const int INF = 0x3f3f3f3f;
int n, m, MT, dp[MBIT][MAXN][MAXN];
int ans[2][MAXN][MAXN];
inline void umax(int& a, const int& b) { a = max(a, b); }
void init() {
  MT = (int)floor(log2((long double)n));
  for (int s = 0; s <= MT; s++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        dp[s][i][j] = -INF;
      }
      dp[s][i][i] = 0;
    }
  }
}
void clr(int z) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      ans[z][i][j] = -INF;
    }
    ans[z][i][i] = 0;
  }
}
bool check(int step) {
  int z = 0;
  clr(z);
  for (int s = 0; s <= MT; s++) {
    if (((step >> s) & 1) == 0) continue;
    z ^= 1;
    clr(z);
    for (int k = 1; k <= n; k++) {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          umax(ans[z][i][j], ans[z ^ 1][i][k] + dp[s][k][j]);
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (ans[z][i][i] > 0) return true;
  }
  return false;
}
int main() {
  int u, v, a, b;
  while (~scanf("%d %d", &n, &m)) {
    init();
    for (int i = 1; i <= m; i++) {
      scanf("%d %d %d %d", &u, &v, &a, &b);
      dp[0][u][v] = a, dp[0][v][u] = b;
    }
    for (int s = 1; s <= MT; s++) {
      for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
          if (dp[s - 1][i][k] == -INF) continue;
          for (int j = 1; j <= n; j++) {
            umax(dp[s][i][j], dp[s - 1][i][k] + dp[s - 1][k][j]);
          }
        }
      }
    }
    int lb = 2, ub = n + 1, mid;
    while (lb <= ub) {
      mid = (lb + ub) >> 1;
      if (check(mid))
        ub = mid - 1;
      else
        lb = mid + 1;
    }
    if (lb >= n + 1) lb = 0;
    printf("%d\n", lb);
  }
  return 0;
}
