#include <fstream>
#define nmax 1001
using namespace std;

struct nod_lista
{
    int vecin;
    nod_lista *link;
};

nod_lista *G[nmax],*Last[nmax];
int CC[nmax][nmax],Viz[nmax],T[nmax],Q[nmax];
int N,M,F;

void adauga(int unde,int ce,int cat)
{
    nod_lista *q=new nod_lista;
    q->vecin=ce;
    q->link=NULL;
    if(!G[unde])
    G[unde]=Last[unde]=q;
    else
    {
        Last[unde]->link=q;
        Last[unde]=q;
    }

    CC[unde][ce]=cat;
}

void citeste()
{
    ifstream f("maxflow.in");
    int x,y,c,i;

    f>>N>>M;

    for(i=1;i<=M;i++)
    {
        f>>x>>y>>c;
        adauga(x,y,c);
    }

    f.close();
}


int BFS(int S,int D)
{
    int p,q,nod,i;
    nod_lista *it;

    for(i=1;i<=N;i++)
    Q[i]=Viz[i]=T[i]=0;

    p=q=0;
    Q[++q]=S;
    Viz[S]=1;

    while(p<=q)
    {
        nod=Q[++p];
        it=G[nod];

        while(it)
        {
            if(!Viz[it->vecin] && CC[nod][it->vecin]>0)
            {
                Viz[it->vecin]=1;
                T[it->vecin]=nod;
                Q[++q]=it->vecin;
            }
            it=it->link;

        }
    }

    if(Viz[D])
    return 1;
    return 0;
}

void satureaza(int S,int D)
{
    int cmin,nod,i;

    cmin=CC[T[D]][D];
    nod=T[D];

    while(nod!=S)
    {
        if(CC[T[nod]][nod]<cmin)
        cmin=CC[T[nod]][nod];

        nod=T[nod];
    }

    nod=D;
    while(nod!=S)
    {
        CC[T[nod]][nod]-=cmin;
        nod=T[nod];
    }

    F+=cmin;
}

void rezolva()
{
    while(BFS(1,N))
    satureaza(1,N);
}

void scrie()
{
    ofstream g("maxflow.out");

    g<<F<<'\n';
    g.close();
}



int main()
{
    //cout << "Hello world!" << endl;
    citeste();
    rezolva();
    scrie();
    return 0;
}