#include <fstream>
#include <bitset>
#include <queue>
#include <cmath>
using namespace std;
int c[1002][1002],f[1002][1002];
bitset<1002> viz;
int n,m,x,y,z;
void citire()
{
    ifstream in("maxflow.in");
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y>>z;
        c[x][y]=z;
    }
}
void afisare()
{
    ofstream out("maxflow.out");
    int vf=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(f[i][j])
            {
                out<<"Fluxul arcului "<<i<<" "<<j<<" "<<f[i][j]<<"\n";
            }
            if(j==n)
                vf+=f[i][j];
        }
    }
    out<<vf;
}
int bfs()
{
    int x;
    queue <int> coada;
    viz[1]=1;
    coada.push(1);
    while(!coada.empty()&&!viz[n])
    {
        x=coada.front();
        coada.pop();
        for(int i=1;i<=n;i++)
        {
            if(!viz[i])
            {
                if(f[x][i]<c[x][i])
                {
                    viz[i]=x;
                    coada.push(i);
                }
                else
                {
                    if(f[i][x]>0)
                    {
                        viz[i]=-x;
                        coada.push(i);
                    }
                }
            }
        }
    }
    return !viz[n];
}
void rezolvare()
{
    int a,b,lg,v;
    int l[1002];
    do
    {
        viz.reset();
        if(bfs())
            return;
        l[0]=n;
        lg=0;
        a=b=10000;
        while(l[lg]!=1)
        {
            lg++;
            l[lg]=viz[l[lg-1]];
            if(l[lg]<0)
                l[lg]=-l[lg];
            if(viz[l[lg-1]]>0)
            {
                a=min(a,c[l[lg]][l[lg-1]]-f[l[lg]][l[lg-1]]);
            }
            else
            {
                if(viz[l[lg-1]]<0)
                {
                    b=min(b,f[l[lg-1]][l[lg]]);
                }
            }
        }
        v=min(a,b);
        for(int i=lg;i>=1;i--)
        {
            if(viz[l[i-1]]>0)
            {
                f[l[i]][l[i-1]]+=v;
            }
            else
            {
                f[l[i-1]][l[i]]-=v;
            }
        }
    }while(1);
}
int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}