Program Maxflow;
 const nmax = 1000;
       mmax = 5000;
       cmax = 110000;
 type drum = array[1..nmax]of 1..nmax;
 var f,g:text; cap:array[1..nmax,1..nmax]of 1..cmax;
     n:2..nmax; m:1..mmax; fl:longint;
     dr:array[1..nmax]of integer;
     dri:array[1..nmax]of integer;
     prim:array[1..nmax]of -1..nmax;
 procedure initiere;
  var x,y,z:integer;
  begin
   assign (f,'maxflow.in'); reset (f);
   assign (g,'maxflow.out'); rewrite (g);
   readln (f,n,m);
   for x:=1 to n do for y:=1 to n do begin
     cap[x,y]:=0;
   end;
   for x:=1 to m do readln (f,y,z,cap[y,z]);
   fl:=0;
  end;
 procedure incheiere;
  begin
   writeln (g,fl);
   close (f); close (g);
  end;
 procedure finddrum (var y:integer; var z:boolean);
  var x,u,v:integer;
  begin
   for x:=1 to n do begin
     dr[x]:=0;
     dri[x]:=0;
     prim[x]:=-1;
   end;
   dr[1]:=1;
   prim[1]:=0;
   z:=true;
   u:=0;
   while z and (prim[n]=-1) do begin
     z:=false;
     u:=u+1;
     for x:=1 to n do
       if (prim[x]=(u-1)) then
         for v:=1 to n do
           if (cap[x,v]>0.1) and (prim[v]=-1) then begin
             z:=true;
             prim[v]:=u;
             dri[v]:=x;
           end;
   end;
   if prim[n]<>-1 then begin
     z:=true;
     u:=n;
     v:=prim[n]+1;
     y:=v;
     for v:=y downto 1 do begin
       dr[v]:=u;
       u:=dri[u];
     end;
   end;
  end;
 procedure getmin (x:integer);
  var y:integer; z,min:longint;
  begin
   min:=maxint;
   for y:=2 to x do begin
     z:=cap[dr[y-1],dr[y]];
     writeln (z,'           ');
     if z<min then min:=z;
   end;
   fl:=fl+min;
   for y:=2 to x do cap[dr[y-1],dr[y]]:=cap[dr[y-1],dr[y]]-min;
  end;
 procedure calcul;
  var y,z:integer; posibil:boolean;
  begin
   repeat
     finddrum (y,posibil);
     if posibil then (getmin (y));
   until not posibil;
  end;
 begin
  initiere;
  calcul;
  incheiere;
 end.