#include <fstream>
#define NMAX 1004
#define INF 10000000000
#define ABS(x) ((x)>0)?(x):(-(x))

using namespace std;

ifstream cin("maxflow.in");
ofstream cout("maxflow.out");

struct nod{int nr,f,c;nod*urm;};
typedef nod*Lista;
Lista lis[NMAX],lisgt[NMAX];

int n,m,marcaj[NMAX],start,stop,sol,vecin[NMAX];

void read();
void inserare(Lista&prim,int,int);
void solve();
bool bfs();
void amelionare_lant();
void inserare(Lista&,int,int);
Lista cauta(Lista,int);
void write();

int main()
{
    read();
    solve();
    write();
    cin.close();cout.close();
    return 0;
}

void write()
{
    Lista aux;
    aux=lisgt[stop];
    while (aux!=NULL)
    {
        sol+=aux->f;
        aux=aux->urm;
    }
    cout<<sol<<'\n';
}

void read()
{
    int i,x,y,c;
    cin>>n>>m;
    for (i=1;i<=n;i++)
    {
        lis[i]=lisgt[i]=NULL;
        marcaj[i]=-1;
    }
    for (i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        inserare(lis[x],y,c);
        inserare(lisgt[y],x,c);
    }
    stop=n;
    start=1;
}

void inserare(Lista&prim,int nr,int c)
{
    Lista aux;
    aux=new nod;
    aux->nr=nr;
    aux->f=0;
    aux->c=c;
    aux->urm=prim;
    prim=aux;
}

void solve()
{
    while (bfs())
        amelionare_lant();
}

int que[NMAX];

bool bfs()
{
    int p=1,u=1;Lista aux;
    que[1]=start;
    marcaj[start]=0;
    while (p<=u)
    {
        aux=lis[que[p]];
        while (aux!=NULL)
        {
            if (marcaj[aux->nr]==-1 && aux->c>aux->f)
            {
                marcaj[aux->nr]=marcaj[que[p]]+1;
                vecin[aux->nr]=que[p];
                que[++u]=aux->nr;
                if (aux->nr==stop)
                    return true;
            }
            aux=aux->urm;
        }
        aux=lisgt[que[p]];
        while (aux!=NULL)
        {
            if (marcaj[aux->nr]==-1 && aux->f>0)
            {
                marcaj[aux->nr]=marcaj[que[p]]+1;
                vecin[aux->nr]=-que[p];
                que[++u]=aux->nr;
                if (aux->nr==stop)
                    return true;
            }
            aux=aux->urm;
        }
        p++;
    }
    return false;
}

Lista noduri[2*NMAX+1];

void amelionare_lant()
{
    int p=stop,v1=INF,v2=INF,v,i=0;
    while (p!=start)
    {
        noduri[++i]=cauta(lis[vecin[p]],p);
        noduri[++i]=cauta(lisgt[p],vecin[p]);
        if (vecin[p]>0)
        {
            if (noduri[i]->c-noduri[i]->f<v1)
                v1=noduri[i]->c-noduri[i]->f;
        }
        else {
            if (noduri[i]->f<v2)
                v2=noduri[i]->f;
        }
        p=ABS(vecin[p]);
    }
    v=(v1<v2)?v1:v2;

    p=stop;i=1;
    while (p!=start)
    {
        if (vecin[p]>0)
        {
            noduri[i]->f+=v;
            noduri[i+1]->f+=v;
        }
        else
        {
            noduri[i]->f-=v;
            noduri[i+1]->f-=v;
        }
        i=i+2;
        p=ABS(vecin[p]);
    }

    for (i=1;i<=n;i++)
        marcaj[i]=-1;
}

Lista cauta(Lista lis,int nr)
{
    while (lis!=NULL)
    {
        if (lis->nr==nr) return lis;
        lis=lis->urm;
    }
    return NULL;
}