#include <bits/stdc++.h>
int n;
using namespace std;
const int rozmiar_kubelka = 356;
void dodajElement(int a, long long b, vector<long long> &S) {
  a += S.size() / 2;
  while (a > 0) {
    S[a] += b;
    a /= 2;
  }
}
long long sumaOdAdoB(int a, int b, vector<long long> &S) {
  a += S.size() / 2;
  b += S.size() / 2;
  long long wynik = 0;
  while (a <= b) {
    if (a & 1) {
      wynik += S[a];
      a++;
    }
    if (!(b & 1)) {
      wynik += S[b];
      b--;
    }
    a /= 2;
    b /= 2;
  }
  return wynik;
}
struct matrix {
  int tab[310][310];

 public:
  matrix();
  void wypisz();
};
void matrix::wypisz() {
  for (int i = 0; i < (n); ++i) {
    for (int j = 0; j < (n); ++j) cout << tab[i][j] << " ";
    cout << endl;
  }
}
matrix::matrix() {
  for (int i = 0; i < (n); ++i)
    for (int j = 0; j < (n); ++j) tab[i][j] = -1000000;
  ;
}
void mult(matrix &B, matrix &C) {
  matrix D = B;
  for (int i = 0; i < (n); ++i) {
    for (int j = 0; j < (n); ++j) {
      for (int k = 0; k < (n); ++k) {
        D.tab[i][j] = max(D.tab[i][j], B.tab[i][k] + C.tab[k][j]);
      }
    }
  }
  B = D;
}
bool czy(matrix &B) {
  for (int i = 0; i < (n); ++i)
    if (B.tab[i][i] > 0) return true;
  return false;
}
int main() {
  int m;
  scanf("%d%d", &n, &m);
  matrix a[10];
  for (int i = 0; i < (m); ++i) {
    int z, b, c, d;
    scanf("%d%d%d%d", &z, &b, &c, &d);
    a[0].tab[z - 1][b - 1] = c;
    a[0].tab[b - 1][z - 1] = d;
  }
  for (int i = 0; i < (n); ++i) a[0].tab[i][i] = 0;
  for (int i = 0; i < (9); ++i) {
    a[i + 1] = a[i];
    mult(a[i + 1], a[i]);
  }
  int it = -1;
  for (int i = 0; i < (10); ++i) {
    if (czy(a[i])) {
      it = i;
      break;
    }
  }
  if (it == -1) {
    printf("0");
    return 0;
  }
  int ans1, ans2 = 1 << it;
  ans1 = 1 << (it - 1);
  matrix moja = a[it];
  matrix mojaMala = a[it - 1];
  for (int i = it - 2; i >= 0; i--) {
    matrix res = mojaMala;
    mult(res, a[i]);
    if (czy(res)) {
      moja = res;
      ans2 = ans1 + (1 << i);
    } else {
      mojaMala = res;
      ans1 += 1 << i;
    }
  }
  printf("%d", ans2);
}
