type muchie=^nod;
     nod=record n:integer; a:muchie; end;

var v:array [1.. 1000] of muchie;
    ad:array[1..1000, 1..1000] of longint;
    poz, tata:array[1..1000] of integer;
    min:array [1..1000] of longint;
    chk:array[1..1000] of boolean;
    t, n, m, i, j, x, y, c, fl, st, dr, b, mmin, bk1, bk2:longint;
    p:muchie;
    ok:boolean;
    f, g:text;


begin
assign (f, 'maxflow.in'); reset (f);
assign (g, 'maxflow.out'); rewrite (g);

read (f, n, m);
for i := 1 to m do
  begin
  read (f, x, y, c);

  ad[x, y]:=c; ad[y, x]:=0;
  if v[x]= nil then begin new (v[x]); v[x]^.n:=y; v[x]^.a:=nil; end
               else begin new(p); p^.n:=y; p^.a:=v[x]; v[x]:=p; end;
  if v[y]= nil then begin new (v[y]); v[y]^.n:=x; v[y]^.a:=nil; end
               else begin new(p); p^.n:=x; p^.a:=v[y]; v[y]:=p; end;
  end;

fl:=0; ok := true;
while ok do
  begin
  ok:=false;                              //initialzari
  st:=1; dr:=1; poz[st]:=1;
  fillchar (chk, n+1, false);
  min[1]:=maxlongint;  chk[1]:=true;

  while (st <= dr) and (ok=false) do
    begin
    p:=v[poz[st]];
    b:=poz[st];
    while (p <> nil) and (ok=false) do
      begin
      if (chk[p^.n] = false) and (ad[b, p^.n]>0) then
        begin
        chk[p^.n]:=true;
        if p^.n = n then
          begin
          ok:=true;
          c:=ad[b, p^.n]; if c<min[st] then mmin:=c else mmin:=min[st];
          t:=t+mmin;
          bk2:=n;
          while st<>0 do
            begin
            bk1:=poz[st];
            dec(ad[bk1, bk2], mmin);
            inc(ad[bk2, bk1], mmin);
            bk2:=bk1; st:=tata[st];
            end;
          end
                    else
          begin
          inc(dr); poz[dr]:=p^.n; tata[dr]:=st;
          c:=ad[b, p^.n]; if c<min[st] then min[dr]:=c else min[dr]:=min[st];
          end;
        end;
      p:=p^.a;
      end;
    inc(st);
    end;
  end;


writeln (g, t);

close (f); close (g);
end.