#include <bits/stdc++.h>
using namespace std;
const int maxl = 3 * 100 + 5;
const int INF = 1000 * 1000 * 1000 + 1;
int n, m;
int dis[maxl][maxl], res[maxl][maxl], tmp[maxl][maxl];
int ans;
void belman(int x) {
  if (x > 1) belman(x / 2);
  if (x == 1) {
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) res[i][j] = dis[i][j];
    return;
  }
  memset(tmp, 63, sizeof tmp);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++)
        tmp[i][j] = min(tmp[i][j], res[i][k] + res[k][j]);
  memset(res, 63, sizeof res);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if ((x & 1))
        for (int k = 0; k < n; k++)
          res[i][j] = min(res[i][j], dis[i][k] + tmp[k][j]);
      else
        res[i][j] = tmp[i][j];
}
bool chk() {
  for (int i = 0; i < n; i++)
    if (res[i][i] < 0) return true;
  return false;
}
int main() {
  cin >> n >> m;
  memset(dis, 63, sizeof dis);
  for (int i = 0; i < m; i++) {
    int a, b, w1, w2;
    cin >> a >> b >> w1 >> w2;
    a--;
    b--;
    dis[a][b] = -w1;
    dis[b][a] = -w2;
  }
  for (int i = 0; i < n; i++) dis[i][i] = 0;
  int first = 1, last = n + 1;
  while (last - first != 1) {
    int mid = (first + last) / 2;
    belman(mid);
    if (chk())
      last = mid;
    else
      first = mid;
  }
  if (last == n + 1)
    ans = 0;
  else
    ans = last;
  cout << ans << endl;
  return 0;
}
