program flux;
const fi='maxflow.in';
      fo='maxflow.out';
var f,g:text;
prec:array of longint;
c:array[1..1000,0..1000] of longint;
x:array of longint;
a:array[1..1000,0..1000] of longint;
n,st,sf,i,nod,ant,t,m,x1,y,z,min,fx:longint;
ok:boolean;
function bf:boolean;
var viz:array of 0..1;
j:longint;
begin
setlength(viz,0);
setlength(viz,n+1);
setlength(x,0);
setlength(x,n+1);
st:=0;
sf:=1;
x[sf]:=1;
viz[1]:=1;
bf:=false;
setlength(prec,0);
setlength(prec,n+1);
prec[1]:=0;
while st<sf do
  begin
  inc(st);
for t:=1  to a[x[st],0] do
   begin
   if (viz[a[x[st],t]]=0) then
   if (c[x[st],a[x[st],t]]<>0) then
     begin
     inc(sf);
     x[sf]:=a[x[st],t];
     viz[x[sf]]:=1;
     prec[sf]:=st;
     if x[sf]=n then
        begin
        bf:=true;
        break;
        end;
    end;
   end;
end;
end;
begin
assign(f,fi);
reset(f);
assign(g,fo);
rewrite(g);
read(f,n,m);
for i:=1 to n do
   begin
   read(f,x1,y,z);
   c[x1,y]:=z;
   c[y,x1]:=0;
   inc(a[x1,0]);
   a[x1,a[x1,0]]:=y;
   inc(a[y,0]);
   a[y,a[y,0]]:=x1;
   end;
ok:=true;
while ok=true do
  begin
  ok:=bf;
  min:=maxlongint;
  ant:=sf;
  nod:=prec[sf];
  while nod<>0 do
  begin
    if c[x[nod],x[ant]]<min then
       min:=c[x[nod],x[ant]];
   ant:=nod;
   nod:=prec[ant];
   end;
  fx:=fx+min;
  ant:=sf;
  nod:=prec[sf];
  while nod<>0 do
    begin
       c[x[nod],x[ant]]:=c[x[nod],x[ant]]-min;
       c[x[ant],x[nod]]:=c[x[ant],x[nod]]+min;
       ant:=nod;
       nod:=prec[ant];
   end;
end;
write(g,fx);
close(f);
close(g);
end.