var v,rezid:array[1..6,1..6]of longint;
    tata:array[1..1001]of integer;
    f:text;
    nod,i,s,d,n,m:integer;
    c,min,fluxu:longint;
    ok:boolean;

procedure citire;
begin
assign(f,'maxflow.in');reset(f);
read(f,n,m);
for i:=1 to m do begin
    read(f,s,d,c);
    v[s,d]:=c;
end;
close(f);
end;

procedure parcurgere;    {in latime}
var viz:array[1..1001]of boolean;
    c:array[1..1001]of integer;
    p,u:integer;
begin
fillchar(viz,sizeof(viz),false);
p:=1;
u:=1;
c[p]:=1;
while p<=u do begin
      nod:=c[p];
      for i:=1 to n do
      if (not viz[i]) and (v[nod,i]-rezid[nod,i]>0) then
         begin
         viz[i]:=true;
         inc(u);
         c[u]:=i;
         tata[i]:=nod;
         end;
      inc(p);
      end;

if viz[d] then ok:=true
          else ok:=false;
end;

procedure prg;
begin
parcurgere;
while ok do begin
      for i:=1 to n do
      if v[i,n]-rezid[i,n]>0 then begin
          min:=v[i,n]-rezid[i,n];
          nod:=i;
          while nod<>s do begin
                if min>v[tata[nod],nod]-rezid[tata[nod],nod] then
                   min:=v[tata[nod],nod]-rezid[tata[nod],nod];
                nod:=tata[nod];
          end;
          nod:=i;
          while nod<>s do begin
                rezid[tata[nod],nod]:=rezid[tata[nod],nod]+min;
                rezid[nod,tata[nod]]:=rezid[nod,tata[nod]]-min;
                nod:=tata[nod];
          end;
          rezid[i,d]:=rezid[i,d]+min;
          rezid[d,i]:=rezid[d,i]-min;
          fluxu:=fluxu+min;
      end;
      parcurgere;
      end;
end;

procedure afisare;
begin
assign(f,'maxflow.out');rewrite(f);
write(f,fluxu);
close(f);
end;

begin
citire;
s:=1;  d:=n;    {s-sursa, d-dest}
prg;
afisare;
end.