#include <cstdio>
#include <string>
#include <math.h>
#define MaxN 1010
#define MAX 0x3f3f3f3f

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

muchie *G[MaxN],*W[MaxN];

int a[MaxN][MaxN],b[MaxN][MaxN],s[MaxN],N,st,f,sw=1,min;

void add(int x,int y)
{
      muchie *aux=new muchie;
      aux->x=y; aux->urm=G[x];
      G[x]=aux;
}

void add2(int x,int y)
{
      muchie *aux=new muchie;
      aux->x=y; aux->urm=W[x];
      W[x]=aux;
}

void cit()
{
      int i,x,y,c,M;
      freopen("maxflow.in","r",stdin);
      scanf("%d%d",&N,&M);
      st=1; f=N;
      for(i=1;i<=M;i++)
      {
            scanf("%d%d%d",&x,&y,&c);
            a[x][y]=c;
            add(x,y);
            add2(y,x);
      }
}

void gasesc_drum()
{
      int p,u,nodc,c[MaxN],i;
      muchie *q=new muchie;
      sw=0;
      //memset(c,0,sizeof(c));
      p=u=1; c[p]=st;
      while(p<=u && c[u]!=f)
      {
            nodc=c[p];
            q=G[nodc];
            while(q)
            {
                  i=q->x;
                  if(a[nodc][i]-b[nodc][i]>0 && !s[i])
                  {
                        s[i]=nodc;
                        c[++u]=i;
                  }
                  q=q->urm;
            }

            q=W[nodc];
            while(q)
            {
                  i=q->x;
                  if(b[nodc][i] && !s[i] && i!=st)
                  {
                        s[i]=nodc;
                        c[++u]=i;
                  }
                  q=q->urm;
            }
            p++;
      }
      if(c[u]==f)
            sw=1;
}

void imbun(int nod)
{
      if(nod!=st)
      {
            if(s[nod]>0)
            {
                  if(min>a[s[nod]][nod]-b[s[nod]][nod])
                        min=a[s[nod]][nod]-b[s[nod]][nod];
                  imbun(s[nod]);
                  b[s[nod]][nod]+=min;
            }
            else
            {
                  if(min>b[nod][abs(s[nod])])
                        min=b[nod][abs(s[nod])];
                  imbun(s[nod]);
                  b[nod][abs(s[nod])]-=min;
            }
      }
}

void det_flux()
{
      do{
            memset(s,0,sizeof(s));
            gasesc_drum();
            if(s[f])
            {
                  min=MAX;
                  imbun(f);
            }
      }while(sw);
}

void afis()
{
      freopen("maxflow.out","w",stdout);
      int i,nr=0;
      for(i=1;i<=N;i++)
            nr+=b[i][f];
      printf("%d\n",nr);
}

int main()
{
      cit();
      det_flux();
      afis();
      return 0;
}