#include<iostream>
#include<fstream>
#include<queue>
using namespace std;

int N, M, x, y, z, maxflow;

int graf_rez[1000][1000];
bool vizitat[1000];
int tata[1000];

void citesteDate();
void scrieRezultat();

bool lantBFS(){
    // initializare date
    for(int i = 1; i <= N; i++){
        vizitat[i] = tata[i] = 0;
    }

    queue<int> coada;
    coada.push(1); // nodul de start
    vizitat[1] = 1;

    while(!coada.empty()){
        int curent = coada.front();
        coada.pop();

        if(curent == N) return true;

        for(int nod = 1; nod <= N; nod ++){
            if(!vizitat[nod] && graf_rez[curent][nod] > 0){

                vizitat[nod] = 1;
                tata[nod] = curent;
                coada.push(nod);
            }
        }
    }
    return false;
}
int main(){
    citesteDate();

    // cat timp se poate construi un lant minim
    while(lantBFS()){

        // pornim verificarea tuturor lanturilor gasite de la nodurile tata ale nodului final
        for(int nod = 1; nod < N; nod ++){
            if(vizitat[nod] && graf_rez[nod][N] > 0) // valoare pozitiva => muchia nu este saturata
            {
                // aflam valoarea minima a fluxului in cadrul lantului curent
                int flux_curent = graf_rez[nod][N];
                // actualizam tatal nodului final in functie de lantul curent gasit
                tata[N] = nod;

                int auxiliar = nod;
                while(tata[auxiliar]){
                    flux_curent = min(flux_curent, graf_rez[tata[auxiliar]][auxiliar]);
                    auxiliar = tata[auxiliar];
                }

                auxiliar = N;
                while(tata[auxiliar]){
                    graf_rez[ tata[auxiliar] ][ auxiliar ] -= flux_curent;
                    graf_rez[ auxiliar ][ tata[auxiliar] ] += flux_curent;
                    auxiliar = tata[auxiliar];
                }
                // actualizam fluxul maxim
                maxflow += flux_curent;
            }
        }
    }
    scrieRezultat();
    return 0;
}
void citesteDate(){
    ifstream f("maxflow.in");

    f>>N>>M;
    while(f>>x>>y>>z){
        graf_rez[x][y] = z;
    }
}
void scrieRezultat(){
    ofstream g("maxflow.out");
    g<<maxflow;
}