#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("maxflow.in");
ofstream g("maxflow.out");

int n,m, x,y,z,flux;
int C[1005][1005], F[1005][1005], T[1005];

void read()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        C[x][y]=z;
    }
}

int BFS(int s,int d)
{
    int p,u,nod,Q[1005];

    memset(T,0,sizeof(T));

    p=u=0;

    Q[p]=s;

    T[s]=-1;

    while(p<=u)
    {
        nod=Q[p];

        for(int i=1;i<=n;i++)
            if(T[i]==0 && C[nod][i]>F[nod][i])
        {
            Q[++u]=i;

            T[i]=nod;

            if(i==d) return i;
        }

        p++;
    }
    return 0;
}

void flux_maxim()
{
    int i,j,r;

    for(flux=0;BFS(1,n);)
    {
        for(i=1;i<=n;i++)
        {
            if(T[i]==0 || C[i][n]<=F[i][n])
                continue;

            r=C[i][n]-F[i][n];

            for(j=i;j!=1 && j;j=T[j])
                r=min(r,C[T[j]][j]-F[T[j]][j]);

            if(r==0) continue;

            F[i][n]+=r;

            F[n][i]-=r;

            for(j=i;j!=1;j=T[j])
            {
                F[T[j]][j]+=r;

                F[j][T[j]]-=r;
            }

            flux+=r;
        }
    }

    g<<flux;
}
int main()
{
    read();

    flux_maxim();

    return 0;
}