program flux_brut;
var     f,g:text;
        t,maxf,min,pas,k,p,n,m,i,j,c,x,y,s,d:longint;
        a:array[1..1000,1..1000] of longint;
        fr:array[1..1000] of byte;
        frz,niv,viz,cd,pred:array[1..1000] of integer;
        v:array[1..5000] of integer;
        bufin,bufout:array[1..1 shl 17] of byte;

function bfs(nod,mark:integer):boolean;
var       p,i,st,sf:longint;
begin
  st:=0; sf:=1; cd[1]:=nod; pred[nod]:=0; viz[nod]:=mark; niv[nod]:=0;
  while st<sf do
    begin
      inc(st);
      for i:=1 to n do
        begin
          if a[cd[st],i]>0 then
            if viz[i]<>mark then
              begin
                inc(sf);
                cd[sf]:=i;
                viz[cd[sf]]:=mark;
                pred[cd[sf]]:=cd[st];
                niv[cd[sf]]:=niv[cd[st]]+1;
              end;
        end;
    end;
  if viz[n]=mark then  bfs:=true
  else bfs:=false;
end;

begin
  assign(f,'maxflow.in'); reset(f);
  assign(g,'maxflow.out'); rewrite(g);
  settextbuf(f,bufin);
  settextbuf(g,bufout);
  readln(f,n,m);
  maxf:=0;
  for i:=1 to m do
    begin
      readln(f,x,y,c);
      a[x,y]:=c;
    end;
  pas:=1;
  while bfs(1,pas) do
    begin
      fr[1]:=1; fr[n]:=1;
      for i:=2 to n-1 do
        fr[pred[i]]:=1;
      k:=0;
      for i:=2 to n-1 do
        if (fr[i]=0) and (a[i,n]>0) then
          begin
            inc(k);
            frz[k]:=i;
          end;
      for t:=1 to k do
        begin
          p:=frz[t];
          v[1]:=n;
          i:=1;
          min:=maxlongint;
          while p<>0 do
            begin
              inc(i);
              v[i]:=p;
              p:=pred[p];
            end;
          for j:=i downto 2 do
            if a[v[j],v[j-1]]<min then min:=a[v[j],v[j-1]];
          for j:=i downto 2 do
            begin
              a[v[j],v[j-1]]:=a[v[j],v[j-1]]-min;
              a[v[j-1],v[j]]:=a[v[j-1],v[j]]+min;
            end;
          maxf:=maxf+min;
        end;
      inc(pas);
    end;
  writeln(g,maxf);
  close(f); close(g);
end.