#include<stdio.h>
FILE *f,*g;
long n,m,i,x,y,z,nr,c[1020],fin[1020],t[4][10020],min,stop,inf,parinte[1020],ok,p,flux,pr,u,st[1020],aux,ind,viz[1020];
int bf()
{ pr=u=1; st[1]=1; viz[1]=ind; stop=1;
  while(pr<=u&&stop)
   { p=c[st[pr]];
     while(p!=0&&stop) 
	  { if(viz[t[1][p]]!=ind&&t[3][p]) 
	     { u++; st[u]=t[1][p]; viz[t[1][p]]=ind; parinte[st[u]]=st[pr]; if(st[u]==n) stop=0; }
        p=t[2][p];
	  }		
	 pr++;
   }
  return st[u]==n;
}  
int main()
{ f=fopen("maxflow.in","r"); g=fopen("maxflow.out","w");
  fscanf(f,"%ld%ld",&n,&m);
  for(i=1;i<=m;i++)
    {  fscanf(f,"%ld%ld%ld",&x,&y,&z);
       if(c[x]==0) { nr++; c[x]=nr; fin[x]=nr; t[1][nr]=y; t[3][nr]=z; }
	   else { nr++; t[2][fin[x]]=nr; t[1][nr]=y; t[3][nr]=z; fin[x]=nr; }
	   aux=x; x=y; y=aux;
	   if(c[x]==0) { nr++; c[x]=nr; fin[x]=nr; t[1][nr]=y; }
	   else { nr++; t[2][fin[x]]=nr; t[1][nr]=y;  fin[x]=nr; }
	}
  inf=1000000; ind=1;
  while(bf())
   { x=n; min=inf;
     while(parinte[x]!=0) 
	  { p=c[parinte[x]]; ok=1;
	    while(ok)
		 { if(t[1][p]==x) 
		    {  if(t[3][p]<min) min=t[3][p]; 
		       ok=0;
            }
           p=t[2][p];
         }
		x=parinte[x];
	  }
	 x=n;
	 while(parinte[x]!=0)
	  { p=c[parinte[x]]; ok=1;
        while(ok)
         { if(t[1][p]==x)
			{ t[3][p]-=min; if(p%2==0) t[3][p-1]+=min; else t[3][p+1]+=min;
              ok=0;
            }
           p=t[2][p];
         }
        x=parinte[x];
      }
	flux+=min; ind++;
   }
   fprintf(g,"%ld",flux);
   fclose(g);
   return 0;
}