#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],*GT[nmax],*TLast[nmax];
int CP[nmax][nmax],Q[nmax],T[nmax],vz[nmax];
int N,M,Flux;

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;
    for(i=1;i<=M;i++)
    {
        f>>x>>y>>c;
        adauga(x,y,c,G,Last);
        adauga(y,x,-c,GT,TLast);
    }

    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;
    while(BFS(1,N))
    {
        q=GT[N];
        while(q)
        {
            if(vz[q->val] && CP[q->val][N]>0)
            {
                T[N]=q->val;
                fmin=inf;
                t=N;
                while(t!=1)//1 adica sursa
                {
                    if(CP[T[t]][t]<fmin)
                    fmin=CP[T[t]][t];
                    t=T[t];
                }

                if(fmin>0)
                {
                    t=N;
                    while(t!=1)
                    {
                        CP[T[t]][t]-=fmin;
                        t=T[t];
                    }
                    Flux+=fmin;
                }
            }
            q=q->link;
        }
    }
}

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

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

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