#include <bits/stdc++.h>
using namespace std;
int in[100];
int dist[9][311][311], res[311][311], t[311][311];
int main() {
  int x, y, a, b, now, ans, i, j, k, l, n, m;
  while (cin >> n >> m) {
    memset(dist, 0xE0, sizeof(dist));
    memset(res, 0xE0, sizeof(res));
    for (i = 0; i < n; ++i) dist[0][i][i] = res[i][i] = 0;
    for (i = 0; i < m; ++i) {
      scanf("%d%d%d%d", &x, &y, &a, &b);
      dist[0][x - 1][y - 1] = a, dist[0][y - 1][x - 1] = b;
    }
    for (i = 1; i < 9; ++i)
      for (j = 0; j < n; ++j)
        for (k = 0; k < n; ++k)
          for (l = 0; l < n; ++l) {
            dist[i][k][l] =
                max(dist[i][k][l], dist[i - 1][k][j] + dist[i - 1][j][l]);
          }
    ans = 0, now = (1 << 8);
    for (i = 8; i >= 0; i--) {
      memset(t, 0xE0, sizeof(t));
      for (j = 0; j < n; ++j)
        for (k = 0; k < n; ++k)
          for (l = 0; l < n; ++l) {
            t[k][l] = max(t[k][l], res[k][j] + dist[i][j][l]);
          }
      for (j = 0; j < n; ++j)
        if (t[j][j] > 0) break;
      if (j == n) {
        ans += now;
        memcpy(res, t, sizeof(t));
      }
      now >>= 1;
    }
    if (ans >= n)
      cout << 0 << endl;
    else
      cout << ans + 1 << endl;
  }
}
