const infile='maxflow.in';
  outfile='maxflow.out';
  maxn=1001;
var c,f:array[1..maxn,1..maxn]of longint;
  t,q:array[1..maxn]of longint;
  n,m,flux,sursa,destin,cf:longint;

 procedure citire;
 var i,j,k:longint;
 begin
   assign(input,infile); reset(input); readln(n,m);
   while(m>0)do begin readln(i,j,k); c[i,j]:=k; dec(m); end;
   close(input);
 end;

 function bf:boolean;
 var ic,sf,u,v:integer;
 begin
   for u:=2 to n do t[u]:=0;
   t[sursa]:=-1;
   sf:=1; q[sf]:=sursa; ic:=1;
   while(ic<=sf)do begin
     u:=q[ic];
     for v:=1 to n do
       if(c[u,v]-f[u,v]>0)and(t[v]=0)then begin
         t[v]:=u; inc(sf); q[sf]:=v;
         end;
     inc(ic);
     end;
   if(t[destin]=0)then bf:=false
   else bf:=true;
 end;

 procedure solve;
 var v,i:longint;
 begin
   sursa:=1; destin:=n; flux:=0;
   while bf do
    for i:=1 to n do
      if(c[i,n]-f[i,n]>0)then begin
        cf:=c[i,n]-f[i,n];
        v:=i;
        while(v<>sursa)do begin
          if(cf>c[t[v],v]-f[t[v],v])then cf:=c[t[v],v]-f[t[v],v];
          v:=t[v];
          end;
        v:=i;
        while(v<>sursa)do begin
         inc(f[t[v],v],cf); dec(f[v,t[v]],cf);
         v:=t[v];
        end;
       inc(f[i,n],cf); dec(f[n,i],cf);
      inc(flux,cf);
      end;
 end;

 procedure afisare;
 begin
   assign(output,outfile); rewrite(output); write(flux); close(output);
 end;

Begin
  citire; solve; afisare;
end.