#include <fstream>

using namespace std;

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

int n,m,C[1004][1004],F[1004][1004],viz[1004],c[1004],L[1004],lg,S;

int Abs(int x)
{
    if (x<0)
        return -x;
    return x;
}

int BFS()
{
    int inc,sf,nc,i;
    inc=sf=1;
    c[1]=1;
    viz[1]=1;
    while (inc<=sf and !viz[n])
    {
        nc=c[inc];
        for (i=1;i<=n;i++)
            if (!viz[i])
            {
                if (F[nc][i]<C[nc][i])
                {
                    c[++sf]=i;
                    viz[i]=nc;
                }
//                else if (F[i][nc]>0)
//                {
//                    c[++sf]=i;
//                    viz[i]=-nc;
//                }
            }
        inc++;
    }
    return !viz[n];
}

void Edmonds_Karp()
{
    int i,a,b,val;
    do
    {
        for (i=1;i<=n;i++)
            viz[i]=0;
        if (BFS())
            return;
        L[0]=n;
        lg=0;
        a=b=200000;
        while (L[lg]!=1)
        {
            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]]);
        }
        val=min(a,b);
        for (i=lg;i>0;i--)
            if (viz[L[i-1]]>0)
                F[L[i]][L[i-1]]+=val;
//            else if (viz[L[i-1]]<0)
//                F[L[i-1]][L[i]]-=val;
    }while (1);
}

int main()
{
    int i,x,y,val;
    f >> n >> m;
    for (i=1;i<=m;i++)
    {
        f >> x >> y >> val;
        C[x][y]=val;
    }
    Edmonds_Karp();
    for (i=1;i<n;i++)
        S+=F[i][n];
    g << S;
    return 0;
}