#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5 + 7;
const int oo = 1e9;
int n, m, c1, c2, ma[301][301], i, j, vis[304];
vector<vector<int> > cache[305];
vector<vector<int> > operator*(vector<vector<int> > a, vector<vector<int> > b) {
  int n = (int)a.size();
  int m = (int)b.size();
  int p = (int)b[0].size();
  vector<vector<int> > c;
  c.resize(n);
  for (int i = 0; i < n; i++) {
    c[i].assign(p, 0);
    for (int j = 0; j < p; j++) {
      c[i][j] = -oo;
      for (int k = 0; k < m; k++) {
        c[i][j] = max(c[i][j], a[i][k] + b[k][j]);
      }
    }
  }
  return c;
}
vector<vector<int> > id(int n) {
  vector<vector<int> > a;
  a.resize(n);
  for (int i = 0; i < n; i++) {
    a[i].assign(n, -oo);
    a[i][i] = 0;
  }
  return a;
}
vector<vector<int> > matrixExp(vector<vector<int> > a, int n) {
  if (vis[n]) return cache[n];
  vis[n] = 1;
  if (n == 0) return id(a.size());
  vector<vector<int> > c = matrixExp(a, n / 2);
  c = c * c;
  if (n % 2 != 0) c = c * a;
  return cache[n] = c;
}
int ok(vector<vector<int> > A, int k) {
  A = matrixExp(A, k);
  for (int i = 0; i < A.size(); i++) {
    if (A[i][i] > 0) return 1;
  }
  return 0;
}
bool check(vector<vector<int> > m) {
  for (int i = 0; i < m.size(); i++) {
    if (m[i][i] > 0) return 1;
  }
  return 0;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  std::cin >> n >> m;
  vector<vector<int> > M;
  M.resize(n, std::vector<int>(n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      M[i][j] = -oo;
    }
    M[i][i] = 0;
  }
  for (int k = 0; k < m; k++) {
    std::cin >> i >> j >> c1 >> c2;
    --i, --j;
    M[i][j] = c1;
    M[j][i] = c2;
  }
  int res = 0;
  vector<vector<int> > curm = id(n);
  for (int i = 9; i >= 0; i--) {
    vector<vector<int> > tmpm(M);
    for (int j = 0; j < i; j++) tmpm = tmpm * tmpm;
    if (!check(tmpm * curm)) curm = curm * tmpm, res += (1 << i);
  }
  if (res == (1 << 10) - 1) res = -1;
  std::cout << res + 1 << '\n';
}
