#include <iostream.h>
#include <fstream.h>
#include <math.h>

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");


int t[1005],n,s,d;
long c[1005][1005], f[1005][1005],flux;




int bf()
{int i,p,u;
    int q[1005];
    memset(t,0,sizeof(t));

    p=u=1;
    q[p]=s;
    t[s]=-1;

    for (;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;
}




int main()
{long min, cc;
    int i,j,m;

    fin>>n>>m;
    s=1;d=n;

    while(fin>>i>>j>>cc)
        c[i][j]+=cc;

    while (bf())


        for (j=1;j<=n;j++)
        { if (t[j]>0 && c[j][n]>f[j][n])
                min=c[j][n]-f[j][n];
            else continue;

            i=j;
            while (i!=s && min)
            {if (min>c[t[i]][i]-f[t[i]][i])
                    min=c[t[i]][i]-f[t[i]][i];
                i=t[i];
            }

            if (min==0) continue;

            f[j][n]+=min;
            f[n][j]-=min;

            flux+=min;

            i=j;

            while (i!=s)
            {f[t[i]][i]+=min;
                f[i][t[i]]-=min;
                i=t[i];
            }



        }

    fout<<flux;
    fout.close();
    return 0;
}