#include <stdio.h>
#define nmax 1001

struct cod
{
int x;
cod *urm;
};

cod *que,*ultim;

void ad(int x)
{
cod *urm = new cod;
urm->x = x;
urm->urm = NULL;
if (que==NULL) que=urm,ultim=que;
else ultim->urm=urm,ultim=urm;
}

struct nod
{
int x,c1,c2;
nod *urm;
};
nod *A[nmax],*B[nmax];

void add(int x,int y,int z)
{
nod *urm = new nod;
urm->x = y;
urm->c1 = z;
urm->c2 = 0;
urm->urm = A[x];
A[x] = urm;
}

int Q[nmax];

int main()
{
freopen("maxflow.in","r",stdin);
freopen("maxflow.out","w",stdout);


int n,m,x,y,z;
scanf("%d %d\n",&n,&m);

while (m)
{
scanf("%d %d %d\n",&x,&y,&z);
if (y!=n) add(x,y,z);
else add(y,x,z);
m--;
}


int flow=0,ok=1,i,max;
nod *w;

while (ok)
{
ok=0;
ad(1);
for (i=1;i<=n;i++) Q[i]=0;
Q[1]=-1;

while (que)
{
w = A[que->x];
while (w!=NULL)
{
//if (w->x!=n)
    if (Q[w->x]==0)
       if (w->c1>w->c2)
          {
          Q[w->x] = que->x;
        //printf("%d\n",w->x);
          B[w->x] = w;
          ad(w->x);
          }
w = w->urm;
}
que = que->urm;
}
//for (i=1;i<=n;i++) printf("%d %d\n",Q[i],i);

w = A[n];
while (w!=NULL)
{
x = w->x;
max = w->c1-w->c2;
while (x!=1 && x!=0)
{
if (B[x]->c1-B[x]->c2<max) max = B[x]->c1-B[x]->c2;
x = Q[x];
}
//     printf("%d\n",max);
if (max && x==1)
{
x = w->x;
w->c2 += max;
while (x!=1) B[x]->c2 += max,x=Q[x];
flow+=max;
ok=1;
}
w=w->urm;
}
}
printf("%d\n",flow);
return 0;
}