UOJ #32.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#define X first
#define Y second
#define mp std::make_pair
#define pb push_back
#define MAX_N 110
#define inf ((ll)0x3f3f3f3f3f3f3f3f)
typedef long long ll;
typedef std::pair<ll, ll> pll;
template <typename T> T chkmn(T &a, T b){
return (a = (a > b ? b : a));
}
template <typename T> T chkmx(T &a, T b){
return (a = (a < b ? b : a));
}
struct Edge *head[MAX_N];
struct Edge{
int to, w, s;
Edge *ne;
Edge(int x, int y, int w, int s) : ne(head[x]), to(y), w(w), s(s){}
};
int n, m;
ll f[MAX_N][MAX_N][2*MAX_N];
bool fl[MAX_N][MAX_N];
std::vector<pll> vec[MAX_N];
int main(){
scanf("%d%d", &n, &m);
for(int i = 1, x, y, w, s; i <= m; i++){
scanf("%d%d%d%d", &x, &y, &w, &s);
head[x] = new Edge(x, y, w, s);
fl[x][y] = true;
}
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
fl[i][j] |= fl[i][k] & fl[k][j];
memset(f, 0x3f, sizeof(f));
f[0][1][n] = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 0; k <= 2*n; k++) if(f[i-1][j][k] < inf){
chkmn(f[i][j][k], f[i-1][j][k]);
for(Edge *e = head[j]; e; e = e->ne) if(k + e->s >= 0)
chkmn(f[i][e->to][k + e->s], f[i-1][j][k] + e->w);
}
for(int i = 1; i <= n; i++)
for(int j = 0; j <= 2 * n; j++) if(f[n][i][j] < inf){
ll mx = inf, mn = -inf - 1;
for(int k = 0; k <= 2 * n; k++) if(f[n - 1][i][k] < inf){
double C = f[n][i][j] - f[n - 1][i][k];
if(k == j){
if(f[n][i][j] >= f[n-1][i][k])
mn = inf, mx = -inf;
}else if(k < j)
chkmn(mx, (ll)ceil(C / (k - j)));
else if(k > j)
chkmx(mn, (ll)floor(C / (k - j)));
}
if(mn < mx - 1)
vec[i].pb(mp(mn + 1, mx));
}
for(int i = 1; i <= n; i++){
std::vector<pll> all; all.clear();
for(int j = 1; j <= n; j++) if(fl[1][j] & fl[j][i])
for(auto k: vec[j])
all.pb(k);
auto cmp = [](pll x, pll y){
return x.X == y.X ? x.Y < y.Y : x.X < y.X;
};
std::sort(all.begin(), all.end(), cmp);
ll ans = 0, lst = -inf;
for(auto j: all){
if(j.X > lst) ans += j.X - lst;
lst = std::max(lst, j.Y);
}
ans += inf - lst;
printf("%lld\n", ans > (1e18) ? -1 : ans);
}
return 0;
}