#include <bits/stdc++.h>
using namespace std;
int n;
struct Graph {
  int a[300][300];
  int *operator[](int x) { return a[x]; }
  void operator*=(Graph &b) {
    static Graph temp;
    int i, j, k, *p;
    for (i = 0; i < n; i++) {
      for (j = 0; j < n; j++) {
        p = &temp[i][j];
        *p = -0x3f3f3f3f;
        for (k = 0; k < n; k++) {
          *p = max(*p, a[i][k] + b[k][j]);
        }
      }
    }
    *this = temp;
  }
  bool check() {
    for (int i = 0; i < n; i++)
      if (a[i][i] > 0) return 1;
    return 0;
  }
} T[20], In, now, temp;
int main() {
  int m, i, j, k, x, y, a, b, ans;
  scanf("%d%d", &n, &m);
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      if (i != j) In[i][j] = -0x3f3f3f3f;
  T[0] = In;
  for (i = 1; i <= m; i++) {
    scanf("%d%d%d%d", &x, &y, &a, &b);
    x--, y--;
    T[0][x][y] = max(T[0][x][y], a), T[0][y][x] = max(T[0][y][x], b);
  }
  for (i = 1; (1 << i) <= n; i++) {
    T[i] = T[i - 1];
    T[i] *= T[i - 1];
  }
  for (k = i--, now = In, ans = 0; i >= 0; i--) {
    temp = now;
    temp *= T[i];
    if (!temp.check()) ans |= 1 << i, now = temp;
  }
  if (ans == (1 << k) - 1)
    puts("0");
  else
    printf("%d\n", ans + 1);
  return 0;
}
