#include <bits/stdc++.h>   using namespace std;   const int N = 305;   long long dist[10][N][N], I[2][N][N];   int main() {     ios::sync_with_stdio(0);     cin.tie(0);     cout.tie(0);     int n, m;     cin >> n >> m;     for (int i = 1; i <= n; i++)       for (int j = 1; j <= n; j++) {         if (i != j) dist[0][i][j] = INT_MIN;         I[0][i][j] = dist[0][i][j];       }     for (int i = 1; i <= m; i++) {       int x, y, c1, c2;       cin >> x >> y >> c1 >> c2;       dist[0][x][y] = c1;       dist[0][y][x] = c2;     }     for (int c = 1; c < 10; c++) {       for (int i = 1; i <= n; i++)         for (int j = 1; j <= n; j++) dist[c][i][j] = dist[c - 1][i][j];       for (int i = 1; i <= n; i++)         for (int k = 1; k <= n; k++)           for (int j = 1; j <= n; j++)             dist[c][i][j] =                 max(dist[c][i][j], dist[c - 1][i][k] + dist[c - 1][k][j]);     }     bool ok = 0;     for (int i = 1; i <= n; i++)       if (dist[9][i][i] > 0) {         ok = 1;         break;       }     if (!ok) {       cout << 0;       return 0;     }     int ans = 1;     for (int bit = 9; bit >= 0; bit--) {       ok = 0;       for (int i = 1; i <= n; i++)         for (int j = 1; j <= n; j++) I[1][i][j] = I[0][i][j];       for (int i = 1; i <= n; i++)         for (int k = 1; k <= n; k++)           for (int j = 1; j <= n; j++)             I[1][i][j] = max(I[1][i][j], I[0][i][k] + dist[bit][k][j]);       for (int i = 1; i <= n; i++)         if (I[1][i][i] > 0) {           ok = 1;           break;         }       if (!ok) {         ans += (1 << bit);         for (int i = 1; i <= n; i++)           for (int j = 1; j <= n; j++) I[0][i][j] = I[1][i][j];       }     }     cout << ans;   }   