#include<fstream>
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
int n,m,viz[1001],q[1001];
int c[1001][1001],flux[1001][1001];
int min(int x,int y)
{
    if(x<y)
    return x;
    else
    return y;
}
int abs(int x)
{
    if(x>0)
    return x;
    else
    return -x;
}
void citire()
{
    int i,x,y,z;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        c[x][y]=z;
    }
}
int bfs()
{
    int p,u,i,x;
    q[0]=1;
    p=u=0;
    viz[1]=1;
    while(p<=u&&!viz[n])
    {
        x=q[p++];
        for(i=1;i<=n;i++)
        if(!viz[i])
        if(flux[x][i]<c[x][i])
        {
            viz[i]=x;
            q[++u]=i;
        }
        else
        if(flux[i][x]>0)
        {
            viz[i]=-x;
            q[++u]=i;
        }
    }
    return !viz[n];
}
void fluxmax()
{
    int i,a,b,lg,v;
    int l[1001];
    do
    {
        for(i=1;i<=n;i++)
        viz[i]=0;
        if(bfs())
        return ;
        l[0]=n;
        lg=0;
        a=b=100000;
        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]]-flux[l[lg]][l[lg-1]]);
            else
            if(viz[l[lg-1]]<0)
            b=min(b,flux[l[lg-1]][l[lg]]);
        }
        v=min(a,b);
        for(i=lg;i>0;i--)
        if(viz[l[i-1]]>0)
        flux[l[i]][l[i-1]]+=v;
        else
        flux[l[i-1]][l[i]]-=v;
    }
    while(1);
}
void afisare()
{
    int i,vf=0;
    for(i=1;i<=n;i++)
    vf+=flux[i][n];
    g<<vf<<"\n";
}
int main()
{
    citire();
    fluxmax();
    afisare();
    return 0;
}