#include <fstream>
#include <stdint.h>
#include <stdlib.h>
#define nmax 1001
#define mmax 5001
using namespace std;
fstream f1("maxflow.in", ios::in);
fstream f2("maxflow.out", ios::out);
int16_t n, m, l[nmax], lg;
int32_t f[nmax][nmax],  c[nmax][nmax], k, prim, ultim, viz[nmax], coada[nmax], v;
const int32_t inf=110000001;
void citire()
{
    int16_t i, x, y;
    int32_t z;
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y>>z;
        c[x][y]=z;
    }
    ///matricea fluxurilor inital pe 0
}
void afisare()
{
    int32_t sum=0;
    int16_t i;
    for(i=1; i<=n; i++)
        sum+=f[i][n];
    f2<<sum<<"\n";
}
void curata()
{
    int16_t i;
    ///viz[i]= nod din care ajungi in i
    for(i=1; i<=n; i++)
        viz[i]=0;
}
void bfs()
{
    int16_t i;
    viz[1]=1;
    prim=1;
    ultim=1;
    k=1;
    coada[prim]=1;
    ///coada retine nodurile, viz val+ semn atribuite la marcaj
    while(k!=0)
    {
        for(i=1; i<=n; i++)
            if(!viz[i])
        {
            if(f[coada[prim]][i]<c[coada[prim]][i]) ///arc nesaturat de la x la i, marchezi i cu +x
            {
                viz[i]=coada[prim];
                k++;
                ultim++;
                coada[ultim]=i;
            }
            else if(f[i][coada[prim]]>0) ///arc cu flux nenul de la i la x, marchezi i cu -x
            {
                viz[i]=-coada[prim];
                k++;
                ultim++;
                coada[ultim]=i;
            }
        }
        prim++;
        k--;
    }
    viz[1]=0;
}
void lant()
{
    l[1]=n;
    v=inf;
    lg=1;

    while(l[lg]!=1)
    {
        lg++;
        l[lg]=abs(viz[l[lg-1]]);
        if(viz[l[lg-1]]>0)
        {
            if(v>c[l[lg]][l[lg-1]]-f[l[lg]][l[lg-1]])
                v=c[l[lg]][l[lg-1]]-f[l[lg]][l[lg-1]];
        }
        else
        {
            if(v>f[l[lg]][l[lg-1]]) v=f[l[lg]][l[lg-1]];
        }
    }
}
void ameliorare()
{
    int16_t i;
    for(i=1; i<lg; i++)
        if(viz[l[i]]>0) f[l[i+1]][l[i]]+=v;
        else  f[l[i+1]][l[i]]-=v;
}
int main()
{
    citire();
    while(1)
    {
        bfs();
        if(!viz[n]) break;
        lant();
        ameliorare();
        curata();
    }
    afisare();
    return 0;
}