#include <cstdio>
#include <queue>
#include <cstring>

FILE* in=fopen("maxflow.in","r");
FILE* out=fopen("maxflow.out","w");

const int Q=1002,INF=1000000000;

int v[Q][Q];
int f[Q][Q];

int n,m,g;

std::queue<int> q;

int frm[Q];

void actualiz(int x)
{
    int p=n;
    while(frm[p])
    {
        f[frm[p]][p]+=x;
        p=frm[p];
    }
}

int minim()
{
    int rez=INF;
    int p=n;

    while(frm[p])
    {
        if(v[frm[p]][p]-f[frm[p]][p]<rez)
            rez=v[frm[p]][p]-f[frm[p]][p];
        p=frm[p];
    }
    return rez;
}

bool bfs()
{
    while(!q.empty())
        q.pop();

    q.push(1);

    int act;
    memset(frm,0,sizeof frm);
    while(!q.empty())
    {
        act=q.front();
        q.pop();

        if(act==n)
            return 1;

        for(int i=2; i<=n; i++)
        {
            if(frm[i]==0 && v[act][i]-f[act][i]>0)
            {
                frm[i]=act;
                q.push(i);
            }
        }
    }
    return 0;
}

int main()
{
    fscanf(in,"%d%d",&n,&m);
    /*
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
            v[i][j]=INF;
    }*/

    int a,b,c;

    for(int i=1; i<=m; i++)
    {
        fscanf(in,"%d%d%d",&a,&b,&c);

        v[a][b]=c;
    }

    int min;

    while(bfs())
    {
        min=minim();
        actualiz(min);
    }

    int rez=0;

    for(int i=1; i<n; i++)
        rez+=f[i][n];

    fprintf(out,"%d",rez);

    return 0;
}