#include <iostream>
#include <cstring>
#include <fstream>
#define inf 1000000;
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
int c[10001][10001],F[10001][10001],T[10001],flux,n,m,x,y,z,s,d;

int BFS(int s,int d)
{
    int p,u,nod,Q[10001];
    memset(T,0,sizeof(T));
    p=u=1;
    Q[p]=s;
    T[s]=-1;
    while(p<=u)
    {
        nod=Q[p];
        for(int i=1;i<=n;i++)
            if(T[i]==0&&c[nod][i]>F[nod][i])
            {Q[++u]=i;T[i]=nod;
             if(i==d)
                return 1;
            }
        p++;

    }
    return 0;

}


void flux_maxim()
{
    int r,i;
    s=1;d=n;
    for(flux=0;BFS(s,d);flux+=r)
    {
        r=inf;
        i=d;
        while(i!=s){
            r=min(r,c[T[i]][i]-F[T[i]][i]);
            i=T[i];
        }
        i=d;
        while(i!=s)
            {F[T[i]][i]+=r;
        F[i][T[i]]-=r;
        i=T[i];}
    }
}

int main()
{f>>n>>m;
for(int i=1;i<=m;i++)
    f>>x>>y>>z,c[x][y]=z;
s=1;
d=n;
flux_maxim();
g<<flux;


    return 0;
}