#include<bits/stdc++.h>
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
int C[1001][1001],viz[1001],F[1001][1001];
int n,m;

int bfs()
{
    int Q[1001],p,u,x;
    Q[0]=1;
    viz[1]=1;
    p=u=0;
    while(p<=u && !viz[n])
    {
        x=Q[p];
        for(int i=1;i<=n;++i)
        {
            if(C[x][i]>F[x][i])
            {
                Q[++u]=i;
                viz[i]=x;
            }
            else
                if(F[i][x]>0)
            {
                Q[++u]=i;
                viz[i]=-x;
            }
        }

        p++;
    }
    return !viz[n];
}

void facut()
{
    int a,b,lg,v,L[1001];
    do{
        memset(viz,0,sizeof(viz));
        if(bfs())
            return;
        L[0]=n;
        lg=0;
        a=b=1000000;
        while(L[lg]!=1)
        {
            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;
    }while(1);
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y,c;
        f>>x>>y>>c;
        C[x][y]=c;
    }
    facut();
    int sol=0;
    for(int i=1;i<=n;++i)
        sol+=F[i][n];
        g<<sol;
}