#include <bits/stdc++.h>
using namespace std;
int gi() {
  int res = 0, s = 1;
  char ch;
  for (ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar())
    ;
  if (ch == '-') s = -1, ch = getchar();
  for (; ch >= '0' && ch <= '9'; ch = getchar()) res = res * 10 + ch - 48;
  return res * s;
}
int n, m, dis[10][305][305], now[305][305], res[305][305];
int main() {
  n = gi(), m = gi();
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) dis[0][i][j] = -0x3f3f3f3f;
  for (int i = 1, x, y, a, b; i <= m; ++i) {
    x = gi(), y = gi(), a = gi(), b = gi();
    dis[0][x][y] = a, dis[0][y][x] = b;
  }
  for (int i = 1; i <= n; ++i) dis[0][i][i] = 0;
  for (int d = 1; d <= 9; ++d) {
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j) dis[d][i][j] = -0x3f3f3f3f;
    for (int k = 1; k <= n; ++k)
      for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
          dis[d][i][j] = (dis[d][i][j] >= dis[d - 1][i][k] + dis[d - 1][k][j]
                              ? dis[d][i][j]
                              : dis[d - 1][i][k] + dis[d - 1][k][j]);
  }
  int ans = 1, flag = 0;
  for (int i = 1; (!flag) && i <= n; ++i)
    if (dis[9][i][i] > 0) flag = 1;
  if (!flag) {
    printf("0\n");
    return 0;
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) now[i][j] = dis[0][i][j];
  for (int d = 9; d >= 0; --d) {
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j) res[i][j] = -0x3f3f3f3f;
    for (int k = 1; k <= n; ++k)
      for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
          res[i][j] = (res[i][j] >= now[i][k] + dis[d][k][j]
                           ? res[i][j]
                           : now[i][k] + dis[d][k][j]);
    flag = 0;
    for (int i = 1; i <= n && !flag; ++i)
      if (res[i][i] > 0) flag = 1;
    if (!flag) {
      ans += (1 << d);
      for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) now[i][j] = res[i][j];
    }
  }
  printf("%d\n", ans + 1);
  return 0;
}
