#include <cstdio>
#include <cstring>
#define MaxN 1002
#define Inf 0x3f3f3f3f
#define infile "maxflow.in"
#define outfile "maxflow.out"

struct edge{
      int x;
      edge *next;
}     *G[MaxN];

int a[MaxN][MaxN],b[MaxN][MaxN];
int t[MaxN],uz[MaxN],Q[MaxN];
int N,M,S,D,flux,sw=1,min;

void add(int x,int y)
{
      edge *q=new edge;
      q->x=y; q->next=G[x]; G[x]=q;
}

void read()
{
      int i,x,y,z;
      scanf("%d%d",&N,&M);
      for(i=1;i<=M;i++)
      {
            scanf("%d%d%d",&x,&y,&z);
            add(x,y); add(y,x);
            a[x][y]+=z;
      }
      S=1; D=N;
}

void BF()
{
      int i,p=1;
      edge *q;
      memset(uz,0,sizeof(uz));
      Q[p]=S; uz[S]=1;
      sw=0;
      for(i=1;i<=p;i++)
            for(q=G[Q[i]];q;q=q->next)
            {
                  if(a[Q[i]][q->x]==b[Q[i]][q->x] || uz[q->x])
                        continue;
                  Q[++p]=q->x;
                  t[q->x]=Q[i];
                  uz[q->x]=1;
                  if(q->x==D)
                  {
                        sw=1;
                        return;
                  }
            }
}

void imbun(int nod)
{
      if(nod!=S)
      {
            if(a[t[nod]][nod]-b[t[nod]][nod]<min)
                  min=a[t[nod]][nod]-b[t[nod]][nod];
            imbun(t[nod]);
            b[t[nod]][nod]+=min;
            b[nod][t[nod]]-=min;
      }
}

void solve()
{
     edge *q;
      do{
            BF();
            for(q=G[D];q;q=q->next)
            {
                  if(a[q->x][D]==b[q->x][D] || !uz[q->x])
                        continue;
                  t[D]=q->x;
                  min=Inf;
                  imbun(D);
                  flux+=min;
            }
      }while(sw);
}

void write()
{
      printf("%d\n",flux);
}

int main()
{
      freopen(infile,"r",stdin);
      freopen(outfile,"w",stdout);

      read();
      solve();
      write();

      fclose(stdin);
      fclose(stdout);
      return 0;
}