#include <iostream>
#include <fstream>
#define INF 110001
using namespace std;
ifstream in("maxflow.in");
ofstream out("maxflow.out");

int n,m;
struct graf{
    int nod;
    struct graf *urm;
}*L[1003],*act; //lista de adiacenta a grafului

int cap[1003][1003]; //capacitatea muchiilor
int flux[1003][1003]; //fluxul prin muchie
int pi[1003]; //parinte noduri
int fluxmax;

void citeste()
{
    int x,y,z;
    in>>n>>m;
    for(int i=1;i<=m;++i)
    {
        in>>x>>y>>z;
        //adauga y la lista x in graf
        act=new graf;
        act->nod=y;
        act->urm=L[x];
        L[x]=act;

        cap[x][y]=z;
    }
}

int bfs(int s,int d)
{
//declaratii
    int viz[1003],cd[1003],inc,sf,nod;
    bool esteDrum=0;
//initializeaza vectorul viz
    for(int i=1;i<=n;++i)
        viz[i]=0;
//adauga sursa in coada
    inc=sf=1;
    cd[sf]=s;
//incepe parcurgerea BFS
    while(inc<=sf)
    {
        nod = cd[inc++];
        for(graf *p=L[nod];p!=NULL;p=p->urm)
        {
            int vec=p->nod;
            if(vec==d && flux[nod][vec]<cap[nod][vec]) //daca avem un drum nesaturat spre destinatie
            {
                esteDrum=1;
            //mareste fluxul prin drum
                //cauta fluxul minim prin drum
                pi[d]=nod;
                int fluxmin=INF;
                for(vec=d;vec!=s;vec=pi[vec])
                    if(fluxmin>cap[pi[vec]][vec]-flux[pi[vec]][vec])
                        fluxmin=cap[pi[vec]][vec]-flux[pi[vec]][vec]; //actualizeaza fluxul minim
                //actualizeaza fluxul prin muchiile din drum
                for(vec=d;vec!=s;vec=pi[vec])
                    flux[pi[vec]][vec]+=fluxmin;
                //SI adauga la fluxul maxim
                fluxmax+=fluxmin;

                //return 1;
            }
            else if(viz[vec]==0 && flux[nod][vec]<cap[nod][vec]) //daca vecinul nu e vizitat si are o muchie nesaturata(flux < capacitate)
            {
                viz[vec]=1; //marcheaza ca vizitat
                pi[vec]=nod; //retine parintele
                cd[++sf]=vec; //pune vecinul in coada
            }
        }
    }
/*
    out<<"FLUX\n";
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
            out<<flux[i][j]<<" ";
        out<<"\n";
    }
*/
//daca nu mai avem niciun drum nesaturat de la sursa la destinatie, ne oprim
    if(!esteDrum)
        return 0;
    return 1;
}

int main()
{
    citeste();

    int sursa=1;
    int destinatie=n;

    int ok=1;
    while(ok)
    {
        ok=bfs(sursa,destinatie);
    }

    out<<fluxmax;

    return 0;
}