#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int f[15][N][N], g[3][N][N];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int k = 0; k < 10; k++)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        if (i != j)
          f[k][i][j] = -1e9;
        else
          f[k][i][j] = 0;
  for (int i = 1; i <= m; i++) {
    int x, y, z, w;
    scanf("%d%d%d%d", &x, &y, &z, &w);
    f[0][x][y] = z;
    f[0][y][x] = w;
  }
  for (int k = 1; k < 10; k++)
    for (int z = 1; z <= n; z++)
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
          f[k][i][j] = max(f[k][i][j], f[k - 1][i][z] + f[k - 1][z][j]);
  int ans = 0, t = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (i != j) g[0][i][j] = -1e9;
  for (int k = 9; k >= 0; k--) {
    int x = ans + (1 << k);
    if (x > n) continue;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        if (i != j)
          g[t][i][j] = -1e9;
        else
          g[t][i][j] = 0;
    for (int z = 1; z <= n; z++)
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
          g[t][i][j] = max(g[t][i][j], g[t ^ 1][i][z] + f[k][z][j]);
    bool flag = 0;
    for (int i = 1; i <= n; i++)
      if (g[t][i][i] > 0) {
        flag = 1;
        break;
      }
    if (flag) continue;
    ans = x;
    t ^= 1;
  }
  printf("%d\n", (ans + 1) % (n + 1));
  return 0;
}
