#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("C:\\Users\\bogda\\Desktop\\facultate\\an 2 sem 1\\AF\\tema 1 lab\\maxflow.in");
ofstream g("C:\\Users\\bogda\\Desktop\\facultate\\an 2 sem 1\\AF\\tema 1 lab\\maxflow.out");
int n,m,flux;
vector<vector<int>> adiacenta, capacitate;
vector<bool> vizitat;
vector<int> tata;
bool bfs(){
    queue<int> coada;
    vizitat.clear();
    tata.clear();
    vizitat.resize(n+1,false);
    tata.resize(n+1,0);

    coada.push(1);
    vizitat[1]=true;
    while(!coada.empty()){
        int nod=coada.front();
        coada.pop();
        if(nod==n)
            continue;
        for (int i = 0; i < adiacenta[nod].size(); ++i) {
            if(!vizitat[adiacenta[nod][i]] && capacitate[nod][adiacenta[nod][i]]>0){
                tata[adiacenta[nod][i]]=nod;
                coada.push(adiacenta[nod][i]);
                vizitat[adiacenta[nod][i]]=true;
            }
        }
    }
    return vizitat[n];
}
int main(){
    int x,y,z;
    f>>n>>m;
    adiacenta.resize(n+1);
    capacitate.resize(n+1,vector<int>(n+1,0));
    for (int i = 0; i < m; ++i) {
        f>>x>>y>>z;
        adiacenta[x].push_back(y);
        adiacenta[y].push_back(x);
        capacitate[x][y]=z;
    }
    while(bfs()){
        for (int i = 0; i < adiacenta[n].size(); ++i) {
            if(!(vizitat[adiacenta[n][i]] && capacitate[adiacenta[n][i]][n]!=0))
                continue;
            int nod=adiacenta[n][i],min=capacitate[nod][n];
            while(tata[nod]!=0){
                if(capacitate[tata[nod]][nod]<min)
                    min=capacitate[tata[nod]][nod];
                nod=tata[nod];
            }
            nod=adiacenta[n][i];
            capacitate[nod][n]-=min;
            capacitate[n][nod]+=min;
            while(tata[nod]!=0){
                capacitate[tata[nod]][nod]-=min;
                capacitate[nod][tata[nod]]+=min;
                nod=tata[nod];
            }
            flux+=min;
        }
    }
    g<<flux;
    return 0;
}