program flux;
type    t2=array[1..1000, 1..1000] of longint;
        nod=record
          pr,del,st:longint;
end;
        t3=array[1..1000] of nod;
var     e,a:t2;b:t3;
        delta,s,t,k,n,i,j:longint;
        f,g:text;

procedure readdata;
var       m,i,j,q:longint;
begin
  assign(f,'maxflow.in'); reset(f);
  readln(f,n,m);
  s:=1; t:=n;
  for k:=1 to m do
    begin
      readln(f,i,j,q);
      a[i,j]:=q;
    end;
  close(f);
end;

function sum(t:integer):longint;
var      i,s:longint;
begin
  s:=0;
  for i:=1 to n do
  s:=s+e[i,t];
  sum:=s;
end;
procedure init_b;
begin
  fillchar(b,sizeof(b),0);
  b[s].st:=1;
  b[s].pr:=+s;
  b[s].del:=maxint;
end;

function activ:longint;
var      i:longint;
begin
  activ:=0;
  for i:=n downto 1 do
    if b[i].st=1 then
      activ:=i;
end;

procedure ford;
var       x,i,d1,q:longint;
begin
  {ford}{miscarea inainte, construim lantul}
  repeat
    x:=activ;
    {dupa G+}
    for i:=1 to n do
      if (b[i].st=0) and (a[x,i]>0) and (e[x,i]<a[x,i]) then
        begin
          d1:=a[x,i]-e[x,i];
          if d1<b[x].del then b[i].del:=d1
            else b[i].del:=b[x].del;
          b[i].st:=1;
          b[i].pr:=+x;
        end;
    {dupa G-}
    for i:=1 to n do
      if (b[i].st=0) and (e[i,x]>0) then
        begin
          d1:=e[i,x];
          if d1<b[x].del then b[i].del:=d1
            else b[i].del:=b[x].del;
          b[i].st:=1;
          b[i].pr:=-x;
        end;
    b[x].st:=2;
  until (b[t].st=1) or (activ=0);
  {miscarea inapoi, extinderea fluxului}
  delta:=0;
  if b[t].st=1 then
    begin
      x:=t;
      delta:=b[t].del;
      repeat
        q:=abs(b[x].pr);
        if b[x].pr>0 then e[q,x]:=e[q,x]+delta;
        if b[x].pr<0 then e[x,q]:=e[x,q]-delta;
        x:=q;
      until x=s;
   end;
end; {ford}

begin
  fillchar(a,sizeof(a),0);
  fillchar(e,sizeof(e),0);
  readdata;
  repeat
    init_b;
    ford;
  until delta=0;
  assign(g,'maxflow.out');
  rewrite(g);
  writeln(g,sum(t));
  close(g);
end.