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

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


nod_lista *G[nmax],*Last[nmax];
int CP[nmax][nmax],Q[nmax],T[nmax],vz[nmax],vecD[nmax];
int N,M,Flux,S,D,nrvec;

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

    if(!G[unde])
    G[unde]=Last[unde]=q;
    else
    {
        Last[unde]->link=q;
        Last[unde]=q;
    }

    CP[unde][ce]=cat;
}

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

    f>>N>>M;
    S=1,D=N;
    for(i=1;i<=M;i++)
    {
        f>>x>>y>>c;
        adauga(x,y,c,G,Last);
       if(y==D)
       vecD[++nrvec]=x;
    }

    f.close();
}

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

    for(i=1;i<=N;i++)
    vz[i]=0;

    p=q=0;
    Q[++q]=S;
    vz[S]=1;
    while(p<q)
    {
        nod=Q[++p];
        it=G[nod];
        while(it)
        {
            if(!vz[it->val] && CP[nod][it->val]>0)
            {
                vz[it->val]=1;
                T[it->val]=nod;
                Q[++q]=it->val;
            }
            it=it->link;
        }
    }

    return vz[D];
}

void rezolva()
{
    nod_lista *q;
    int t,fmin,i,nod;
    while(BFS(S,D))
    {
        for(i=1;i<=nrvec;i++)
        {
            nod=vecD[i];
            if(vz[nod] && CP[nod][D]>0)
            {
                T[D]=nod;
                fmin=inf;
                t=D;
                while(t!=S)//1 adica sursa
                {
                    if(CP[T[t]][t]<fmin)
                    fmin=CP[T[t]][t];
                    t=T[t];
                }

                if(fmin>0)
                {
                    t=D;
                    while(t!=S)
                    {
                        CP[T[t]][t]-=fmin;
                        t=T[t];
                    }
                    Flux+=fmin;
                }
            }
        }
    }
}

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

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

int main()
{
    citeste();
    rezolva();
    scrie();
    return 0;
}