#include <bits/stdc++.h>
using namespace std;
int N, M;
int g[11][312][312];
int f[312][312], s[312][312];
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= N; ++i)
    for (int j = 1; j <= N; ++j) g[0][i][j] = 1000002012;
  for (int i = 1; i <= M; ++i) {
    int x, y, c1, c2;
    scanf("%d%d%d%d", &x, &y, &c1, &c2);
    g[0][x][y] = -c1;
    g[0][y][x] = -c2;
  }
  for (int p = 1; p <= 10; ++p) {
    for (int i = 1; i <= N; ++i)
      for (int j = 1; j <= N; ++j) g[p][i][j] = g[p - 1][i][j];
    for (int k = 1; k <= N; ++k)
      for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
          g[p][i][j] = min(g[p - 1][i][k] + g[p - 1][k][j], g[p][i][j]);
  }
  bool flag = 0;
  for (int i = 1; i <= N; ++i)
    if (g[10][i][i] < 0) flag = 1;
  if (!flag) {
    puts("0");
    return 0;
  }
  int ans = 0;
  for (int i = 1; i <= N; ++i)
    for (int j = 1; j <= N; ++j)
      if (i != j)
        f[i][j] = 1000002012;
      else
        f[i][j] = 0;
  int T = 2048;
  for (int p = 10; p >= 0; --p) {
    T = T >> 1;
    bool flag = 0;
    for (int i = 1; i <= N; ++i)
      if (g[p][i][i] < 0) flag = 1;
    if (flag) continue;
    memcpy(s, f, sizeof(f));
    for (int i = 1; i <= N; ++i)
      for (int k = 1; k <= N; ++k)
        for (int j = 1; j <= N; ++j)
          s[i][j] = min(f[i][k] + g[p][k][j], s[i][j]);
    flag = 0;
    for (int i = 1; i <= N; ++i)
      if (s[i][i] < 0) flag = 1;
    if (!flag) {
      ans += T;
      memcpy(f, s, sizeof(s));
    }
  }
  cout << ans + 1;
  return 0;
}
