#include <bits/stdc++.h>
using namespace std;
const int maxn = 300 + 10;
const int maxm = maxn * (maxn - 1);
const int inf = 1e9 + 10;
const int maxk = 10;
int d[maxk][maxn][maxn];
int t[maxn][maxn], nd[maxn][maxn];
int n, m;
void work(int c[][maxn], int a[][maxn], int b[][maxn]) {
  for (int i = (1); i <= (n); ++i)
    for (int j = (1); j <= (n); ++j) c[i][j] = -inf;
  for (int k = (1); k <= (n); ++k)
    for (int i = (1); i <= (n); ++i)
      for (int j = (1); j <= (n); ++j)
        c[i][j] = max(c[i][j], a[i][k] + b[k][j]);
}
bool judge(int a[][maxn]) {
  for (int i = (1); i <= (n); ++i)
    if (a[i][i] > 0) return 1;
  return 0;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (1); i <= (n); ++i)
    for (int j = (1); j <= (n); ++j) {
      d[0][i][j] = (i == j ? 0 : -inf);
    }
  int u, v;
  for (int i = (1); i <= (m); ++i)
    scanf("%d%d", &u, &v), scanf("%d%d", &d[0][u][v], &d[0][v][u]);
  for (int i = (1); i <= (n); ++i)
    for (int j = (1); j <= (n); ++j) t[i][j] = d[0][i][j];
  for (int v = (0); v <= (8); ++v) {
    work(d[v + 1], d[v], d[v]);
  }
  if (!judge(d[9])) {
    printf("0\n");
    return 0;
  }
  int ans = 1;
  for (int v = 8; v >= 0; --v) {
    work(nd, d[v], t);
    if (!judge(nd)) {
      for (int i = (1); i <= (n); ++i)
        for (int j = (1); j <= (n); ++j) t[i][j] = nd[i][j];
      ans += (1 << v);
    }
  }
  printf("%d\n", ans + 1);
}
