#include <stdio.h>
#include <algorithm>
#include <queue>
#define NMAX 1005

using namespace std;

int N,M,S,D;
int viz[NMAX];
int L[NMAX];
int F[NMAX][NMAX],C[NMAX][NMAX];
int FLUX;
queue<int> Q;

void read()
{
    scanf("%d %d\n",&N,&M);
    S=1;
    D=N;

    for (int i=1;i<=M;i++)
    {
        int a,b,c;
        scanf("%d %d %d\n",&a,&b,&c);
        C[a][b]=c;
    }
}

int bfs()
{
    Q.push(S);
    viz[S]=1;
    while (!Q.empty())
    {
        int x=Q.front();
        Q.pop();

        for (int i=1;i<=N;i++)
            if (!viz[i])
                if (F[x][i]<C[x][i])
                {
                    viz[i]=x;
                    Q.push(i);
                }
                else
                    if (F[i][x]>0)
                    {
                        viz[i]=-x;
                        Q.push(i);
                    }
    }

    return !viz[D];
}

void EK()
{
    int a,b,lg,v;
    while (!bfs())
    {
        L[0]=D;
        a=b=10000;
        lg=0;

        while (L[lg]!=S)
        {
            lg++;
            L[lg]=abs(viz[L[lg-1]]);
            if (viz[L[lg-1]]>0)
                a=min(a,C[L[lg]][L[lg-1]]-F[L[lg]][L[lg-1]]);
            else
                if (viz[L[lg-1]]<0)
                    b=min(b,F[L[lg-1]][L[lg]]);
        }

        v=min(a,b);
        for (int i=lg;i>0;i--)
            if (viz[L[i-1]]>0)
                F[L[i]][L[i-1]]+=v;
            else F[L[i-1]][L[i]]-=v;

        for (int i=1;i<=N;i++) viz[i]=0;
    }

    for (int i=1;i<=N;i++)
        FLUX+=F[i][D];

    printf("%d\n",FLUX);
}

int main()
{
    freopen ("maxflow.in","r",stdin);
    freopen ("maxflow.out","w",stdout);

    read();
    EK();

    fclose(stdin);
    fclose(stdout);
    return 0;
}