#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int t[1005],n,s,d;
long c[1005][1005], f[1005][1005],flux;

int bfs()
{
    int i,p,u;
    int q[1005];
    memset(t,0,sizeof(t));
    p=u=1;
    q[p]=s;
    t[s]=-1;
    for(p=1;p<=u;p++)
    {
        for(i=1;i<=n;i++)
            if(!t[i] && c[q[p]][i]>f[q[p]][i])
            {
                u++;
                q[u]=i;
                t[i]=q[p];
                if(i==d)
                    return 1;
            }
    }
    return 0;
}
long long int minn,cc;
int i,j,m;
int main()
{
    fin>>n>>m;
    s=1;
    d=n;
    while(m--)
    {
        fin>>i>>j>>cc;
        c[i][j]=c[i][j]+cc;
    }
    while(bfs())
    {
        for(j=1;j<=n;j++)
        {
            if(t[j]>0 && c[j][n]>f[j][n])
                minn=c[j][n]-f[j][n];
            else
                continue;
            i=j;
            while(i!=s && minn)
            {
                if (minn>c[t[i]][i]-f[t[i]][i])
                    minn=c[t[i]][i]-f[t[i]][i];
                i=t[i];
            }
            if (minn==0)
                continue;
            f[j][n]=f[j][n]+minn;
            f[n][j]=f[n][j]-minn;
            flux=flux+minn;
            i=j;
            while (i!=s)
            {
                f[t[i]][i]+=minn;
                f[i][t[i]]-=minn;
                i=t[i];
            }
        }
    }
    fout<<flux;
    fin.close();
    fout.close();
    return 0;
}