!min-cost max flow

#include <bits/stdc++.h>

#define fastRead ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define in(s) freopen(s, "r", stdin)
#define out(s) freopen(s, "w", stdout)

using namespace std;

typedef long long ll;

const int MAXN = 1000;

vector<ll> g[MAXN], c[MAXN], f[MAXN], lvl, p, used, rev[MAXN], pr;
vector<ll> cost[MAXN], d;

void func(int k, int l, int w, int cost1, int t)
{
    g[k].push_back(l);
    f[k].push_back(0);
    c[k].push_back(w);
    rev[k].push_back(t);
    cost[k].push_back(cost1);
}

void fu(int k, int l, int w, int cost1)
{
    func(k, l, w, cost1, (int)g[l].size());
    func(l, k, 0, -cost1, (int)g[k].size() - 1);
}

int main()
{
    assert(in("mincost.in"));
    assert(out("mincost.out"));
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int k, l, w, cost1;
        scanf("%d %d %d %d", &k, &l, &w, &cost1);
        fu(k, l, w, cost1);
    }
    ll res = 0;
    while (true)
    {
        d.assign(n + 1, 1e16);
        used.assign(n + 1, 0);
        p.assign(n + 1, -1);
        pr.assign(n + 1, -1);
        d[1] = 0;
        for (int i = 0; i <= n + 1; i++)
            for (int v = 1; v <= n; v++)
                for (int j = 0; j < (int)g[v].size(); j++)
                    if (c[v][j] > f[v][j] && d[g[v][j]] > d[v] + cost[v][j])
                    {
                        d[g[v][j]] = d[v] + cost[v][j];
                        p[g[v][j]] = v;
                        pr[g[v][j]] = j;
                    }
        if (p[n] == -1)
            break;
        ll ans = c[p[n]][pr[n]] - f[p[n]][pr[n]];
        int v = p[n];;
        while (v != 1)
        {
            ans = min(ans, 1LL * c[p[v]][pr[v]] - f[p[v]][pr[v]]);
            v = p[v];
        }
        v = n;
        while (v != 1)
        {
            res += cost[p[v]][pr[v]] * ans;
            f[p[v]][pr[v]] += ans;
            f[v][rev[p[v]][pr[v]]] -= ans;
            v = p[v];
        }
    }
    cout << res;
    return 0;
}