#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
int i,j,x,y,c,n,m,s,d,q[1001],viz[1001],F[1001][1001],C[1001][1001];
void read()
{
    f>>n>>m;
    s=1;
    d=n;
    for(i=1;i<=m;++i)
    {
        f>>x>>y>>c;
        C[x][y]=c;
    }
}
int bfs()
{
    int i,u,p,x;
    p=1;
    u=1;
    q[p]=s;
    viz[s]=1;
    while(p<=u && !viz[d])
    {
        x=q[p];
        ++p;
        for(i=1;i<=n;++i)
        if(!viz[i])
            {if(F[x][i]<C[x][i])
            {
                q[++u]=i;
                viz[i]=x;
            }
            else if(F[i][x]>0)
            {
                viz[i]=-x;
                q[++u]=i;
            }}

    }
    if(viz[d])
        return 0;
    return 1;
}
void ek()
{
    int i,a,b,lg,v;
    int L[1001];
    do
    {
        for(i=1;i<=n;++i)
        viz[i]=0;
            if(bfs())
            return;
        lg=0;
        L[lg]=d;
        a=110001;
        b=110001;
        while(L[lg]!=s)
        {
            ++lg;
            L[lg]=viz[L[lg-1]];
            if(L[lg]<0)
                L[lg]=-L[lg];
            if(viz[L[lg-1]]>0)
                a=min(a,C[L[lg]][L[lg-1]]-F[L[lg]][L[lg-1]]);
            else
                b=min(b,F[L[lg-1]][L[lg]]);
        }
        v=min(a,b);
        for(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);
}
void afis()
{   int s;
    s=0;
    for(i=1;i<=n;++i)
        s=s+F[i][d];
    g<<s<<'\n';
}
int main()
{
    read();
    ek();
    afis();
    return 0;
}