#include <iostream>
#include <fstream>
#define nmax 1000
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int n,m,cost[nmax+5][nmax+5],tata[nmax+5],vmin=0x3f3f3f3f,ok=0,siz=0,aux[nmax+5];
struct nod
{
    int info;
    nod *urm;
}*v[nmax+5],*d,*e[nmax+5];
void dfs(int x, bool viz[nmax+5])
{
    cout<<x<<"\n";
    nod *c=v[x];
    aux[x]=vmin;
    while(c->urm && ok)
    {
        c=c->urm;
        if(cost[x][n]>0)
        {
            tata[n]=x;
            if(cost[x][n]<vmin)
                vmin=cost[x][n];
            ok=0;
            cout<<vmin<<"\n\n";
            break;
        }
        if(!viz[c->info] && cost[x][c->info]>0)
        {
            viz[c->info]=1;
            tata[c->info]=x;
             if(cost[x][c->info]<vmin)
                vmin=cost[x][c->info];
            cout<<vmin<<"\n\n";
            dfs(c->info,viz);
        }
        viz[c->info]=0;
    }
    if(ok)
        vmin=aux[tata[x]];
}
int main()
{
    int x,y,z;
    bool viz[nmax+5];
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->info=i;
        v[i]->urm=0;
        viz[i]=0;
    }
    while(fin>>x>>y>>z)
    {
        if(!v[x]->urm)
        {
            d=new nod;
            d->urm=0;
            d->info=y;
            v[x]->urm=d;
            e[x]=d;
        }
        else
        {
            d=new nod;
            d->urm=0;
            d->info=y;
            e[x]->urm=d;
            e[x]=d;
        }
        cost[x][y]=z;
    }
    viz[1]=1;
    while(!ok)
    {
        ok=1;
        dfs(1,viz);
        x=n;
        while(x!=1)
        {
            cost[tata[x]][x]-=vmin;
            cost[x][tata[x]]+=vmin;
            x=tata[x];
        }
        if(vmin!=0x3f3f3f3f)
        siz+=vmin;
        vmin=0x3f3f3f3f;
    }
    fout<<siz;
    return 0;
}