//
// Created by avoro on 12/8/2025.
//
// flux maxim
// se da un graf rezidual sa se determine fluuxl maxim de la s la t
//graf rezidual -> un graf ponderat unde ponderea reprezinta o capacitate
///ford fulkerson
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <unordered_map>

using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
vector<vector<int>> graf;
unordered_map<int,unordered_map<int,int>> capac;
vector<int> viz;
vector<int> parent;
int flux_total,flux;
int n,m,x,y,c,s=1,t;

void resetviz() {
    for (int i = 1; i<=n; i++) {
        viz[i] = 0;
    }
}

int existaDrum(int nod, int p, int f) {
    parent[nod] = p;
    viz[nod] = 1;
    if (nod == t) return f;
    for (auto vecin: graf[nod]) {
        if (viz[vecin] == 0 && capac[nod][vecin]>0) {
            int flux_nou = min(f, capac[nod][vecin]);
            int rez = existaDrum(vecin,nod,flux_nou);
            if (rez >0 )
                return rez;
        }
    }
    return 0;
}

int main() {
    fin>>n>>m;
    graf.resize(n+1);
    viz.assign(n+1, 0);
    parent.assign(n+1,-1);
    for (int i = 1; i<=m ; i++) {
        fin>>x>>y>>c;
        graf[x].push_back(y);
        graf[y].push_back(x); // muchie inversa pentru graful rezidual
        capac[x][y] += c;
        capac[y][x] += 0;
    }
    t = n;
    flux = existaDrum(s,-1,INT_MAX);
    while (flux > 0) {
        resetviz();
        flux_total+= flux;
        int nod = t;
        while (nod != s) {
            int parinte = parent[nod];
            capac[parinte][nod] -= flux;
            capac[nod][parinte] +=flux;
            nod = parinte;
        }
        flux = existaDrum(s,-1,INT_MAX);
    }
    fout<<flux_total<<'\n';
}