program maximum_flow;
  type lista=^celula;
       celula=record
                info:longint;
                capacity:longint;
                next,prev:lista;
              end;
  var n,m,i:longint;
      a,curent:array [1..1000] of lista;
      r:lista;
      x,y,z:longint;
      h:array [1..1000] of longint; {inaltimile}
      e:array [1..1000] of longint; {surplusurile}
      f:array [1..1000,1..1000] of longint; {fluxuri}
      cf:array [1..1000,1..1000] of longint; {capacitati reziduale}
      q:lista;
      l:lista;
      height:longint;

procedure push(x,y:longint);
  var min:longint;
  begin
    min:=e[x];                           {impinge lichid prin muchia x-y}
    if cf[x,y]<min then min:=cf[x,y];
    f[x,y]:=f[x,y]+min;
    f[y,x]:=-f[x,y];
    e[x]:=e[x]-min;
    e[y]:=e[y]+min;
    cf[x,y]:=cf[x,y]-min;
    cf[y,x]:=cf[y,x]+min;
  end;

procedure lift(x:longint);
  var b:lista;
      min:longint;
  begin
    min:=2*n;
    b:=a[x];                    {ridica nodul x}
    while b<>nil do
      begin
        if (h[b^.info]<min)and(cf[x,b^.info]>0) then min:=h[b^.info];
        b:=b^.next;
      end;
    h[x]:=1+min;
  end;

procedure discharge(x:longint);
  var v:lista;
  begin
    while e[x]>0 do
      begin
        v:=curent[x];                     {descarca nodul de surplus}
        if v=nil then
          begin
            lift(x);
            curent[x]:=a[x];
          end
        else if (cf[x,v^.info]>0)and(h[x]=h[v^.info]+1)then
          push(x,v^.info) else curent[x]:=curent[x]^.next;
      end;
  end;

begin
  assign(input,'maxflow.in');
  reset(input);
  assign(output,'maxflow.out');
  rewrite(output);

  readln(n,m);
  for i:=1 to m do
    begin
      readln(x,y,z);
      cf[x,y]:=z;
      new(r);
      r^.info:=y;        {constructia grafului}
      r^.capacity:=z;
      r^.next:=a[x];
      a[x]:=r;
      new(r);
      r^.info:=x;
      r^.capacity:=0;
      r^.next:=a[y];
      a[y]:=r;
    end;

  h[1]:=n;
  q:=a[1];
  while q<>nil do
    begin
      f[1,q^.info]:=q^.capacity;         {initializare}
      f[q^.info,1]:=-q^.capacity;
      e[q^.info]:=q^.capacity;
      e[1]:=e[1]-q^.capacity;
      cf[1,q^.info]:=0;
      cf[q^.info,1]:=q^.capacity;
      q:=q^.next;
    end;

  for i:=n-1 downto 2 do
    begin
      new(r);
      r^.info:=i;
      r^.next:=l;
      r^.prev:=nil;
      if l<>nil then l^.prev:=r;       {lista nodurilor}
      l:=r;
    end;

  for i:=1 to n do curent[i]:=a[i];

  q:=l;
  while q<> nil do
    begin
      height:=h[q^.info];
      discharge(q^.info);
      if h[q^.info]>height then         {descarca pe rind nodurile cu}
        begin                           {surplus, daca se schimba inaltimea}
          if q<>l then
            if q^.next=nil then
              begin
                q^.prev^.next:=q^.next;
                new(r);
                r^.info:=q^.info;
                r^.next:=l;
                r^.prev:=nil;
                l^.prev:=r;
                l:=r;
                q:=l;
              end else
              begin
                q^.next^.prev:=q^.prev;  {nodul se muta la inceputul listei}
                q^.prev^.next:=q^.next;
                 new(r);
                r^.info:=q^.info;
                r^.next:=l;
                r^.prev:=nil;
                l^.prev:=r;
                l:=r;
                q:=l;

              end;
        end;
      q:=q^.next;
    end;

  writeln(e[n]);
  close(output);
end.