!mincost Форд-Беллман (spfa)

#ifdef ONPC
    # define _GLIBCXX_DEBUG
    #define deb(a) cerr << "========" << #a << " = " << a << endl;
#else
    #define deb(a)
#endif
#define sz(a) (int)(a).size()
#include <bits/stdc++.h>

using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;

struct Edge
{
    int from, to;
    ll c, f, w;
    Edge(int from, int to, ll c, ll f, ll w):
        from(from),
        to(to),
        c(c),
        f(f),
        w(w) {}
};

const int N = 100005;
const ll INF = 1e18 + 239;
vector<Edge> e;
vector<int> g[N];
int used[N], pr[N], t;
ll d[N];


void upd(int ind, int f)
{
    e[ind].f += f;
    e[ind ^ 1].f -= f;
}

ll cost;

int solve()
{
    int n;
    if (!(cin >> n))
        return 1;
    int m, s;
    cin >> m;
    s = 0;
    t = n - 1;
    e.clear();
    for (int i = 0; i < n; i++)
        g[i].clear();
    for (int i = 0; i < m; i++)
    {
        int x, y, z, q;
        cin >> x >> y >> z >> q;
        x--;
        y--;
        g[x].push_back(sz(e));
        e.push_back(Edge(x, y, z, 0, q));
        g[y].push_back(sz(e));
        e.push_back(Edge(y, x, 0, 0, -q));
    }
    cost = 0;
    while (true)
    {
        for (int i = 0; i < n; i++)
            d[i] = INF, used[i] = 0;
        d[s] = 0;
        queue<int> q;
        q.push(s);
        used[s] = 1;
        while (sz(q))
        {
            int v = q.front();
            q.pop();
            used[v] = 0;
            for (int ind : g[v])
            {
                if (e[ind].f < e[ind].c && d[e[ind].to] > d[v] + e[ind].w)
                {
                    d[e[ind].to] = d[v] + e[ind].w;
                    pr[e[ind].to] = ind;
                    if (!used[e[ind].to])
                    {
                        used[e[ind].to] = 1;
                        q.push(e[ind].to);
                    }
                }
            }
        }
        if (d[t] < INF)
            break;
        int v = t;
        ll mn = INF;
        ll sum = 0;
        while (v != s)
        {
            sum += e[pr[v]].w;
            mn = min(mn, e[pr[v]].c - e[pr[v]].f);
            v = e[pr[v]].from;
        }
        cost += sum * mn;
        v = t;
        while (v != s)
        {
            upd(pr[v], mn);
            v = e[pr[v]].from;
        }
    }
    cout << cost << endl;
    return 0;
}

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int TET = 1e9;
    //cin >> TET;
    while (TET--)
    {
        if (solve())
            break;
        #ifdef ONPC
            cout << "\n__________________________" << endl;
        #endif
    }
    #ifdef ONPC
        cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
    #endif
}
close