const infile='maxflow.in';
  outfile='maxflow.out';
  maxn=1001;
  maxm=5001;
  sursa=1;
  infinit=maxlongint;
type nod=^pnod;
  pnod=record  inf:longint; next:nod; end;
var a:array[1..maxn]of nod; {lista vecinilor}
  c,f:array[1..maxn,1..maxn]of longint;{capacitatea si fluxul}
  tata,q,cf:array[1..maxn]of longint;
  {tatal nodului in coada, coada, capaciatea reziduala}
  n,m,destin:longint;
  fmax:longint;

 procedure citire;
 var i,j,k:longint;
   p:nod;
 begin
   assign(input,infile); reset(input); readln(n,m);
   while(m>0)do begin
    readln(i,j,k); dec(m); c[i,j]:=k;
    new(p); p^.inf:=j; p^.next:=a[i]; a[i]:=p;
    end;
   close(input);
 end;

 function minim(x,y:longint):longint;
 begin
   if(x<y)then minim:=x
   else minim:=y;
 end;

 function bf:longint;
 var ic,sf,i:longint;
   r:nod;
 begin
   for i:=2 to n do begin cf[i]:=0; tata[i]:=0; end;
   tata[1]:=-1; cf[sursa]:=infinit;
   ic:=1; sf:=1; q[sf]:=sursa;
   while(ic<=sf)and(cf[destin]=0)do begin
     r:=a[q[ic]];
     while(r<>nil)do begin
       if(c[q[ic],r^.inf]>f[q[ic],r^.inf])and(tata[r^.inf]=0)then begin
         tata[r^.inf]:=q[ic];
         cf[r^.inf]:=minim(cf[q[ic]],c[q[ic],r^.inf]-f[q[ic],r^.inf]);
         inc(sf); q[sf]:=r^.inf;
         end;
       r:=r^.next;
       end;
     inc(ic);
     end;
   bf:=cf[destin];
 end;

 procedure solve;
 var v,min:longint;
 begin
  fmax:=0; destin:=n;
  repeat
    min:=bf;
    if(min=0)then
    else begin
      inc(fmax,min);
      v:=destin;
      while(v<>sursa)do begin
        inc(f[tata[v],v],min); dec(f[v,tata[v]],min);
        v:=tata[v];
        end;
      end;
  until min=0;
 end;

 procedure scrie;
 begin
   assign(output,outfile); rewrite(output); write(fmax);
   close(output);
 end;

begin
citire; solve; scrie;
end.