TEAMBOOK max-flow

#include <bits/stdc++.h>
using long_type = long long;
#define long long_type
#define all(x) begin(x), end(x)
using namespace std;

const int   max_n       = 1 << 17;
const int   int_inf     = 0x3f3f3f3f;
const long  long_inf    = 0x3f3f3f3f3f3f3f3f;
const int   source      = max_n - 1;
const int   sink        = max_n - 2;

struct edge {
    long c, f;
    int u, r;
    edge(int _u, long _c, int _r) :
        c(_c),
        f(0),
        u(_u),
        r(_r) {}
};

struct flow {
    long lim;
    int ptr[max_n], fw[max_n], bw[max_n];
    vector<pair<int, int>> where;
    vector<edge> g[max_n];
    vector<int> bfsg[max_n];

    void add_edge(int v, int u, long w) {
        where.emplace_back(v, (int)g[v].size());
        g[v].emplace_back(u, w, (int)g[u].size());
        g[u].emplace_back(v, 0, (int)g[v].size() - 1);
    }
    void bfs(int from, int dist[]) {
        fill(all(ptr), 0);
        fill(dist, dist + max_n, int_inf);
        queue<int> q;
        q.push(from);
        dist[from] = 0;
        while (q.size()) {
            int v = q.front();
            q.pop();
            for (int u : bfsg[v]) {
                if (dist[u] > dist[v] + 1) {
                    dist[u] = dist[v] + 1;
                    q.push(u);
                }
            }
        }
    }
    long dfs(int v, long mn) {
        if (v == sink) {
            return mn;
        }
        for (; ptr[v] < (int)g[v].size(); ++ptr[v]) {
            edge &e = g[v][ptr[v]];
            edge &r = g[e.u][e.r];
            if (fw[e.u] != fw[v] + 1 || bw[e.u] != bw[v] - 1 || e.c - e.f < lim) {
                continue;
            }
            long d = dfs(e.u, min(mn, e.c - e.f));
            if (d) {
                e.f += d;
                r.f -= d;
                return d;
            }
        }
        return 0;
    }
    long max_flow() {
        long sum = 0;
        for (lim = 1 << 30; lim >= 1; lim >>= 1) {
            while (1) {
                for (int i = 0; i < max_n; ++i) {
                    bfsg[i].clear();
                }
                for (int i = 0; i < max_n; ++i) {
                    for (edge e : g[i]) {
                        if (e.c - e.f >= lim) {
                            bfsg[i].push_back(e.u);
                        }
                    }
                }
                bfs(source, fw);
                if (fw[sink] == int_inf) {
                    break;
                }
                for (int i = 0; i < max_n; ++i) {
                    bfsg[i].clear();
                }
                for (int i = 0; i < max_n; ++i) {
                    for (edge e : g[i]) {
                        if (e.c - e.f >= lim) {
                            bfsg[e.u].push_back(i);
                        }
                    }
                }
                bfs(sink, bw);
                long cur = dfs(source, long_inf);
                while (cur) {
                    sum += cur;
                    cur = dfs(source, long_inf);
                }
            }
        }
        return sum;
    }
} f;


int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#else
#define TASK "flow2"
    assert(freopen(TASK ".in", "r", stdin));
    assert(freopen(TASK ".out", "w", stdout));
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int v, u, w;
        cin >> v >> u >> w;
        f.add_edge(v, u, w);
    }
    assert((int)f.where.size() == m);
    f.add_edge(source, 1, long_inf);
    f.add_edge(n, sink, long_inf);
    cout << f.max_flow() << "\n";
    for (int i = 0; i < m; ++i) {
        pair<int, int> p = f.where[i];
        edge &e = f.g[p.first][p.second];
        cout << e.f << "\n";
    }
    cerr << 1000 * clock() / CLOCKS_PER_SEC << endl;
    return 0;
}