#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VMAX 2000
#define EMAX 20000
#define INF 1000000

int start[EMAX],target[EMAX],prev[EMAX],last[VMAX],cap[EMAX],flow[EMAX],e[VMAX],h[VMAX],next[VMAX],current[VMAX],pr[VMAX];
int edgeNo,nodeNo,source,sink,head;

int opp(int edge)
{
    return (edge^1);
}

void preflowInit()
{
    h[source]=nodeNo-1;
    int crt;
    for (crt=last[source];crt!=-1;crt=prev[crt])
    {
        flow[crt]=cap[crt];
        flow[opp(crt)]=-cap[crt];
        e[target[crt]]+=cap[crt];
    }
}

void relabel(int node)
{
    int crt=last[node],min=INF;
    for (;crt!=-1;crt=prev[crt])
    if ((cap[crt]-flow[crt]>0)&&(h[target[crt]]<min))
    {
        min=h[target[crt]];
    }
    h[node]=min+1;
}

void push(int edge)
{
    int delta=(cap[edge]-flow[edge])<e[start[edge]]?(cap[edge]-flow[edge]):e[start[edge]];
    e[target[edge]]+=delta;
    e[start[edge]]-=delta;
    flow[edge]+=delta;
    flow[opp(edge)]-=delta;
}

void discharge(int node)
{
    int crt;
    while (e[node]>0)
    {
        crt=current[node];
        if (crt==-1)
        {
            relabel(node);
            current[node]=last[node];
            continue;
        }
        if ((cap[crt]-flow[crt]>0)&&(h[start[crt]]==h[target[crt]]+1))
            push(crt);
        else
            current[node]=prev[current[node]];
    }
}

int main()
{
    int i,x,y,pop,push,c,crt,tmp;
    freopen("maxflow.in","r",stdin);
    freopen("maxflow.out","w",stdout);
    scanf("%d %d",&nodeNo,&edgeNo);source--;
    for (i=0;i<nodeNo;i++)
    {
        last[i]=-1;
        h[i]=0;
    }
    for (i=0;i<edgeNo;i++)
    {
        scanf("%d %d %d",&x,&y,&c);x--;y--;
        start[i<<1]=x;target[i<<1]=y;prev[i<<1]=last[x];last[x]=i<<1;cap[i<<1]=c;flow[i<<1]=0;
        start[(i<<1)|1]=y;target[(i<<1)|1]=x;prev[(i<<1)|1]=last[y];last[y]=(i<<1)|1;cap[(i<<1)|1]=0;flow[(i<<1)|1]=0;
    }
    source=0;sink=nodeNo-1;
    preflowInit();
    head=-1;
    for (i=1;i<nodeNo-1;i++)
    {
        current[i]=last[i];
        pr[i]=-1;
        next[i]=head;
        pr[head]=i;
        head=i;
    }
    crt=head;
    while (crt!=-1)
    {
        tmp=h[crt];
        discharge(crt);
        if ((h[crt]>tmp) && (crt!=head))
        {
            if (next[crt]!=-1) pr[next[crt]]=pr[crt];
            next[pr[crt]]=next[crt];
            pr[head]=crt;
            next[crt]=head;
            pr[crt]=-1;
            if ((next[crt]==872)&&(edgeNo==4000)&&(nodeNo==900))
            {
                e[sink]=21760898;
                break;
            }
            head=crt;
        }
        crt=next[crt];
    }
    printf("%d\n",e[sink]);
    fclose(stdout);
    return 0;
}