Диниц

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <math.h>
#include <cmath>
#include <string>
#include <time.h>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <string.h>
#include <stack>
using namespace std;

#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
#define cin in
#define cout out
#define pii pair<int,int>
#define ll long long
#define db double
#define ld long double
#define uset unordered_set
#define umap unordered_map
#define vec vector
#define ms multiset
#define pb push_back
#define pll pair<ll,ll>
#define pdd pair<ld, ld>
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define pnn pair<Node*, Node*>
#define uid uniform_int_distribution

ifstream in("input.txt");
ofstream out("output.txt");

const int MAX_N = 500, INF = 2e9;
int n, m, S, T;
vector<int> g[MAX_N];
int C[MAX_N][MAX_N], F[MAX_N][MAX_N], d[MAX_N], it[MAX_N];

bool bfs() {
    memset(d, 255, sizeof(d));

    queue<int> q;
    d[S] = 0;
    q.push(S);

    while(!q.empty()) {
        int v = q.front();
        q.pop();

        for(int to: g[v]) {
            if(F[v][to] < C[v][to] && d[to] == -1) {
                d[to] = d[v] + 1;
                q.push(to);
            }
        }
    }

    return d[T] != -1;
}

//block flow
int dfs(int v, int min_C) {
    if(v == T || min_C == 0)
        return min_C;

    for(int to = g[v][it[v]]; it[v] < g[v].size(); to = g[v][it[v]]) {
        if(d[to] == d[v] + 1) {
            int next = dfs(to, min(min_C, C[v][to] - F[v][to]));
            if(next != 0) {
                F[v][to] += next;
                F[to][v] -= next;
                return next;
            }
        }

        it[v]++;
    }

    return 0;
}

ll dinic() {
    ll max_flow = 0;
    while(bfs()) {
        memset(it, 0, sizeof(it));
        int flow = dfs(S, INF);

        while(flow != 0) {
            max_flow += flow;
            flow = dfs(S, INF);
        }
    }
    return max_flow;
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--;b--;
        C[a][b] = c;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    S = 0; T = n-1;

    cout << dinic();
}