#include <bits/stdc++.h>
using namespace std;
const int maxn = 333;
int g[maxn][maxn], a[maxn][maxn], d[maxn][maxn];
void mul(int x[maxn][maxn], int y[maxn][maxn], const int n) {
  static int c[maxn][maxn], mid[maxn][maxn];
  for (int _n(n), i(0); i < _n; i++)
    for (int _n(n), j(0); j < _n; j++) c[i][j] = -1011111111;
  for (int _n(n), i(0); i < _n; i++)
    for (int _n(n), j(0); j < _n; j++)
      for (int _n(n), k(0); k < _n; k++)
        c[i][j] = max(c[i][j], x[i][k] + y[k][j]);
  memcpy(x, c, sizeof(c));
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int _n(n), i(0); i < _n; i++)
    for (int _n(n), j(0); j < _n; j++) g[i][j] = i == j ? 0 : -1011111111 / 20;
  for (int _n(m), it(0); it < _n; it++) {
    int i, j;
    scanf("%d%d", &i, &j);
    --i, --j;
    scanf("%d%d", &g[i][j], &g[j][i]);
  }
  int lo = 2, hi = n + 1, ans = 0;
  while (lo <= hi) {
    const int mid = (lo + hi) >> 1;
    memcpy(a, g, sizeof(g));
    for (int _n(n), i(0); i < _n; i++)
      for (int _n(n), j(0); j < _n; j++)
        d[i][j] = i == j ? 0 : -1011111111 / 20;
    for (int i = mid; i; i >>= 1, mul(a, a, n))
      if (i & 1) mul(d, a, n);
    bool ok = true;
    for (int _n(n), i(0); i < _n; i++)
      if (d[i][i] > 0) {
        ok = false;
      }
    if (ok)
      lo = mid + 1;
    else
      hi = mid - 1, ans = mid;
  }
  printf("%d\n", ans);
  return 0;
}
