#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define lmax 1005
#define INFINIT 0x3f3f3f
using namespace std;
unsigned short int viz[lmax];
struct nod
{
    short int inf;
    nod *urm,*prec;
};
struct element
{
    unsigned int flow,cost;
};
element M[lmax][lmax];
unsigned int SUM=0,cul=1;
FILE *f=fopen("maxflow.in","r"),*g=fopen("maxflow.out","w");
short int n,m;
void read()
{
    unsigned int x,y,cost;
    short int i;
    fscanf(f,"%hd %hd",&n,&m);
    for(i=1; i<=m; i++)
        fscanf(f,"%u %u %u",&x,&y,&cost),M[x][y].cost=cost;
}
void show_matrice()
{
    unsigned short int i,j;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
            cout<<"["<<M[i][j].flow<<","<<M[i][j].cost<<"] ";
        cout<<"\n";
    }
}
void addcoada(nod *&ultim,nod *prec,unsigned short int val)
{
    nod *nou;
    nou=new nod;
    nou->inf=val;
    nou->prec=prec;
    nou->urm=NULL;
    ultim->urm=nou;
    ultim=nou;
}
void make_coada(nod *&prim,nod *&ultim,unsigned short int val)
{
    prim=new nod;
    prim->inf=val;
    prim->urm=NULL;
    prim->prec=NULL;
    ultim=prim;
}
void showprec(nod *lol)
{
    if(lol->prec)
        showprec(lol->prec);
    cout<<lol->inf<<" ";
}
void find_minim(nod *lol,unsigned  int &minim)
{
    if(lol->prec)
    {
        if( (M[lol->prec->inf][lol->inf].cost-M[lol->prec->inf][lol->inf].flow)<minim)
            minim=M[lol->prec->inf][lol->inf].cost-M[lol->prec->inf][lol->inf].flow;
        find_minim(lol->prec,minim);
    }
}
void update_flows(nod *lol,unsigned int minim)
{
    if(lol->prec)
    {
        M[lol->prec->inf][lol->inf].flow+=minim;
        update_flows(lol->prec,minim);
    }
}
bool breadth_first(unsigned short int inc,unsigned short int sf,short int cul)
{
    nod *prim,*ultim,*p;
    unsigned int minim=INFINIT;
    bool gasit=0;
    make_coada(prim,ultim,inc);
    viz[inc]=cul;
    p=prim;
    for(; p && !gasit; p=p->urm)
    {
        for(unsigned short int i=1; i<=n; i++)
            if(M[p->inf][i].flow<M[p->inf][i].cost && viz[i]!=cul)
            {
                addcoada(ultim,p,i);
                if(i==n)
                    gasit=1;
                viz[i]=cul;
            }
    }
    find_minim(ultim,minim);
    update_flows(ultim,minim);
    if(gasit)
        SUM+=minim;
    return gasit;
}
int main()
{
    read();
    while(breadth_first(1,n,cul))
        cul++;
    fprintf(g,"%u",SUM);
    fclose(f);
    fclose(g);
    return 0;
}