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

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

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;
      }
}

void gasesc_drum()
{
      int p,u,nodc,c[MaxN],i;
      sw=0;
      memset(c,0,sizeof(c));
      p=u=1; c[p]=st;
      while(p<=u && c[u]!=f)
      {
            nodc=c[p];
            for(i=1;i<=N && !sw;i++)
            {
                  if(a[nodc][i]-b[nodc][i]>0 && !s[i])
                  {
                        s[i]=nodc;
                        c[++u]=i;
                  }
                  else
                        if(a[i][nodc] && b[i][nodc] && !s[i] && i!=st)
                        {
                              s[i]=nodc;
                              c[++u]=i;
                        }
            }
            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;
}