#include <iostream>
#include<fstream>
#include<vector>
#include<queue>

using namespace std;

ifstream f("maxflow.in");
ofstream g("maxflow.out");

int N,M;
int capacitate[1001][1001], flux_curent[1001][1001];
vector<vector<int>> adj, i_adj;
int element, nod, flux_maxim, flux_minim, firstelem, k=0;
vector<int> tata;
vector<bool> vizitat;
queue<int> coada;


int creare_lant()
{

    while(!coada.empty()) coada.pop();

    tata.clear();
    tata.resize(N+1,0);
    vizitat.clear();
    vizitat.resize(N+1,false);

    coada.push(1);
    vizitat[1]=true;

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

        for(auto p:adj[firstelem])
        {
            if(vizitat[p]==false && capacitate[firstelem][p] > flux_curent[firstelem][p])
            {
                coada.push(p);
                vizitat[p]=true;
                tata[p]=firstelem;
                if(p==N) return 1;
            }
        }

        for(auto p:i_adj[firstelem])
        {
            if(vizitat[p]==false && flux_curent[p][firstelem]>0)
            {
                coada.push(p);
                vizitat[p]=true;
                tata[p]=-firstelem;
                if(p==N) return 1;
            }
        }

    }
        return 0;

}

void revizuire_flux()
{
    for(auto p:i_adj[N])
        if(capacitate[p][N] >= flux_curent[p][N] && vizitat[p]==true)

    {
        element = N;
        tata[N] = p;
        flux_minim=INT_MAX;

        while (element!=1) // caut care este fluxul minim cu care poate fi modificat lantul curent
        {
            nod = tata[element];
            if(nod > 0)
            {
                int ramas = capacitate[nod][element] - flux_curent[nod][element];
                if(flux_minim > ramas)
                    flux_minim = ramas;
            }

            else if (flux_minim > flux_curent[element][-nod])
                flux_minim = flux_curent[element][-nod];

            element = nod;
            if(element < 0)
                element = -element;


        }

        element = N;

        while (element!=1) // dupa ce am aflat fluxul minim, actualizez fluxurile
        {
            nod = tata[element];
            if(nod > 0)
            {
                    flux_curent[nod][element] += flux_minim;
            }

            else flux_curent[element][-nod] -= flux_minim;

            element = nod;
            if(element < 0)
                element = -element;


        }

        flux_maxim = flux_maxim + flux_minim;

    }
}



int main()
{
    f>>N>>M;

    adj.resize(N+1);
    i_adj.resize(N+1);

    tata.resize(N+1);
    vizitat.resize(N+1);
    int cant,x,y;

    for(int i=0;i<M;i++)
    {
        f>>x>>y>>cant;
        adj[x].push_back(y);
        i_adj[y].push_back(x);
        capacitate[x][y]=cant;
        flux_curent[x][y]=0;
    }

    flux_maxim=0;


    while (creare_lant())
    {
        //cout<<creare_lant()<<endl;
        revizuire_flux();
    }

    g<<flux_maxim;

}