const nmax=20;
      inf=maxint;
type info=record
     c,g:integer;
     end;
var a:array[1..nmax,1..nmax]of info;
    n,i:1..nmax;
    m:array[1..nmax]of integer;
    gata:boolean;
    v:word;
    f:text;

procedure init;
var m,i,j,z:word;
    x,y:1..nmax;
begin
assign(f,'maxflow.in');reset(f);
readln(f,n,m);
for i:=1 to n do
 for j:=1 to n do begin
  a[i,j].c:=-1;
  a[i,j].g:=0;
  end;
for i:=1 to m do begin
 readln(x,y,z);
 a[x,y].c:=z;
 end;
 close(f);
end;

procedure etichete(k:word);
var j:word;
begin
if not gata then
 for j:=1 to n do
  if (a[k,j].c>=0)and(m[j]=0)and(a[k,j].c<>a[k,j].g)then
     begin
        m[j]:=k;
        if j=n then gata:=true
               else etichete(j);
               end
   else if(a[j,k].c>=0)and(m[j]=0)and(a[j,k].g<>0)then
    begin
    m[j]:=-k;
    etichete(j);
    end
 end;

procedure marire;
var x,y,i,l,min1,min2,min:word;
    d:array[1..nmax]of 1..nmax;
  procedure genlant(k:word);
  var aux:integer;
  begin
  aux:=m[k];
  if aux<>n+1 then begin
   if aux>0 then begin
    if min1>a[aux,k].c-a[aux,k].g then min1:=a[aux,k].c-a[aux,k].g
    end
    else if min2>a[k,-aux].g then min2:=a[k,-aux].g;
    genlant(abs(aux));
    l:=l+1;
    d[l]:=k;
    end
    else begin d[1]:=1; l:=1; end
    end;
begin
min1:=inf;
min2:=inf;
genlant(n);
if min1<2 then min:=min1
          else min:=min2;
for i:=1 to l-1 do begin
 x:=d[i];
 y:=d[i+1];
 if m[y]>0 then a[x,y].g:=a[x,y].g+min
           else a[y,x].g:=a[y,x].g-min
           end;
 v:=v+min;
 end;

begin
init;
v:=0;
repeat
for i:=1 to n do m[i]:=0;
m[1]:=n+1;
gata:=false;
etichete(1);
if m[n]<>0 then marire;
until m[n]=0;
writeln(v);
readln;
end.