#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
int mtx[10][300][300];
int cur[2][300][300];
int n, m, ans;
void mult(int a[300][300], int b[300][300], int c[300][300]) {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      c[i][j] = -INF;
    }
    c[i][i] = 0;
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      for (int k = 0; k < n; ++k) {
        c[i][j] = max(c[i][j], a[i][k] + b[k][j]);
      }
    }
  }
}
void init() {
  ans = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      mtx[0][i][j] = -INF;
      cur[0][i][j] = -INF;
    }
    mtx[0][i][i] = 0;
    cur[0][i][i] = 0;
  }
}
void solve() {
  scanf("%d %d", &n, &m);
  init();
  for (int i = 1, l, r; i <= m; ++i) {
    scanf("%d %d", &l, &r);
    --l, --r;
    scanf("%d %d", &mtx[0][l][r], &mtx[0][r][l]);
  }
  for (int i = 1; i < 10; ++i) {
    mult(mtx[i - 1], mtx[i - 1], mtx[i]);
  }
  int now = 0;
  for (int pw = 9; pw >= 0; --pw) {
    bool ok = 1;
    mult(cur[now], mtx[pw], cur[now ^ 1]);
    now ^= 1;
    for (int i = 0; i < n; ++i) {
      if (cur[now][i][i] > 0) {
        ok = 0;
      }
    }
    if (ok) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          cur[now ^ 1][i][j] = cur[now][i][j];
        }
      }
      ans += (1 << pw);
    }
    now ^= 1;
  }
  if (++ans > n) {
    ans = 0;
  }
  printf("%d\n", ans);
}
int main() {
  int tt = 1;
  while (tt--) {
    solve();
  }
  return 0;
}
