#include <bits/stdc++.h>
using namespace std;
const int maxn = 300 + 7, INF = 1e9;
int n, m;
int d[10][maxn][maxn];
int t[maxn][maxn];
int nd[maxn][maxn];
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 is_ok(int a[][maxn]) {
  for (int i = 1; i <= n; ++i) {
    if (a[i][i] > 0) return true;
  }
  return false;
}
void print(int t[][maxn]) {
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      cout << t[i][j] << ' ';
    }
    cout << endl;
  }
  cout << endl << endl;
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (i == j)
        d[0][i][j] = 0;
      else
        d[0][i][j] = -INF;
    }
  }
  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    cin >> 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 i = 0; i < 9; ++i) {
    work(d[i + 1], d[i], d[i]);
  }
  if (!is_ok(d[9])) {
    cout << 0 << endl;
    return 0;
  }
  int ans = 1;
  for (int i = 8; i >= 0; --i) {
    work(nd, d[i], t);
    if (!is_ok(nd)) {
      for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
          t[i][j] = nd[i][j];
        }
      }
      ans += (1 << i);
    }
  }
  cout << ans + 1 << endl;
  return 0;
}
