type mat=array[1..1000,1..1000] of longint;
     vek=array[1..5000] of longint;
     vak=array[1..5000] of boolean;
var x:mat; f:text; i,n,k,m,a,b,c,max,min,w,s,j:longint; cs,os,v:vek; jr:vak;  t:boolean;
procedure df(k:longint);
  var i:longint;
  begin
    if k<n then begin
    for i:=1 to n do
      if (x[k,i]>0)and(not jr[i]) then begin t:=true; inc(c); cs[c]:=i; jr[i]:=true; os[i]:=k; jr[i]:=true; end;
      j:=j+1;
      df(cs[j]);
    end;  end;
begin
  assign(f,'maxflow.in');
  reset(f);
  readln(f,n,m);
  for i:=1 to m do begin
    readln(f,a,b,c);
    x[a,b]:=c;
    end;
  close(f);
  max:=0;
  for i:=1 to n do
   max:=max+x[i,n];
  repeat
  for i:=1 to n do
  jr[i]:=false;
  c:=0;
  t:=false;
  c:=1; cs[c]:=1;
  jr[1]:=true;
  j:=1;
  df(1);
  i:=n;
  w:=1;
  v[w]:=i;
  repeat
  i:=os[i];
    inc(w); v[w]:=i;
  until i=1;
  min:=111111;
  for i:=w downto 2 do
  if x[v[i],v[i-1]]<min then min:=x[v[i],v[i-1]];
  for i:=w downto 2 do
    x[v[i],v[i-1]]:=x[v[i],v[i-1]]-min;
  until not t;
  s:=0;
  for i:=1 to n do
    s:=s+x[i,n];
  max:=max-s;
  assign(f,'maxflow.out');
  rewrite(f);
  write(f,max);
  close(f);
end.