flows

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

const ull INF = 1e18;

#define min(a, b) ((a) > (b) ? (b) : (a))

struct edge {
    int b, u, c, f, back;
};
vector<vector<edge>> g;

void add_edge(int a, int b, int u, int c) {
    g[a].push_back ({b, u, c, 0, (int)g[b].size()});
    g[b].push_back ({a, 0, -c, 0, (int)g[a].size() - 1});
}

ull mincostmaxflow(int s, int t, int n) {
    ull flow = 0, cost = 0;
    while (1) {
        vector<ull> id(n, 0), d(n, INF), q(n), p(n);
        vector<ull> p_edge(n);

        int qh = 0, qt = 0;
        q[qt++] = s, d[s] = 0;
        while (qh != qt) {
            int v = q[qh++], i = 0;
            id[v] = 2;
            qh %= n;
            for (auto & e : g[v]) {
                if (e.f < e.u && d[v] + e.c < d[e.b]) {
                    d[e.b] = d[v] + e.c;
                    if (id[e.b] == 0) {
                        q[qt++] = e.b;
                        qt %= n;
                    } else if (id[e.b] == 2) {
                        if (--qh == -1)  qh = n - 1;
                        q[qh] = e.b;
                    }
                    id[e.b] = 1, p[e.b] = v, p_edge[e.b] = i;
                }
                ++i;
            }
        }

        if (d[t] == INF)  break;
        ull dflow = INF;
        for (int v = t; v != s; v = p[v]) {
            int pv = p[v], pr = p_edge[v];
            dflow = min(dflow, g[pv][pr].u - g[pv][pr].f);
        }
        for (int v = t; v != s; v = p[v]) {
            int pv = p[v], pr = p_edge[v], r = g[pv][pr].back;
            g[pv][pr].f += dflow;
            g[v][r].f -= dflow;
            cost += g[pv][pr].c * dflow;
        }
        flow += dflow;
    }

    return cost;
}

int main() {
    int n, m, a, b, c, cost;
    cin >> n >> m;
    g.resize(n);
    while (m--) {
        cin >> a >> b >> c >> cost;
        --a, --b;
        add_edge(a, b, c, cost);
    }
    cout << mincostmaxflow(0, n - 1, n);
    return 0;
}