#include <bits/stdc++.h>
using namespace std;
int n, m;
struct M {
  int a[301][301];
  M() { memset(a, 0, sizeof(a)); }
};
M mul(M& a, M& b) {
  M ret;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) {
      ret.a[i][j] = -1000000000;
      for (int k = 0; k < n; ++k)
        ret.a[i][j] = max(ret.a[i][j], a.a[i][k] + b.a[k][j]);
    }
  return ret;
}
M a[10];
M cur, nw;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) a[0].a[i][j] = -1000000000;
  for (int i = 0; i < n; ++i) a[0].a[i][i] = 0;
  cur = a[0];
  for (int i = 0; i < m; ++i) {
    int x, y, c, d;
    scanf("%d%d%d%d", &x, &y, &c, &d);
    --x;
    --y;
    a[0].a[x][y] = c;
    a[0].a[y][x] = d;
  }
  for (int z = 0; z < 9; ++z) a[z + 1] = mul(a[z], a[z]);
  int ans = 1;
  for (int z = 9; z >= 0; --z) {
    nw = mul(cur, a[z]);
    bool awesome = false;
    for (int i = 0; i < n; ++i)
      if (nw.a[i][i] > 0) {
        awesome = true;
        break;
      }
    if (!awesome) {
      ans += (1 << z);
      cur = nw;
    }
  }
  if (ans <= n)
    printf("%d\n", ans);
  else
    printf("0\n");
}
