program edmondkarp;
 type ftip=array[1..1000,1..1000] of longint;
      ftip2=array[1..1000,0..1000] of longint;
      ftip3=array[1..1000] of longint;
      ftip4=array[-1..1000] of longint;
 const inf=maxlongint div 4;
 var a,b:text;
   i,j,k,n,x,y,nk,s,t,v,u:longint;
   C:ftip;
   E:ftip2;
   P:ftip3;
   Fmaj:ftip;
   f,m,fprec:longint;
   function min(i,j:longint):longint;
    begin
     if i<j then exit(i) else exit(j);
    end;
   procedure BFS;
   var u,v,i,j:longint;
    mMaj:ftip3;
    q:ftip4;
    begin
    for i:=1 to k do
     mmaj[i]:=0;
      for u:=1 to k do
       P[u]:=-1;
      P[s]:=-2;
      Mmaj[s]:=inf;
      q[0]:=0;
      q[-1]:=0;
      for i:=1 to k do
       q[i]:=0;
      inc(q[0]);
      inc(q[-1]);
      q[q[0]]:=s;
      inc(q[0]);
       while q[-1]<>q[0] do
        begin
         u:=q[q[-1]];
         inc(q[-1]);
         if q[-1]=q[0]+1 then exit;
         for i:=1 to E[u,0] do
          begin
           v:=E[u,i];
           if(C[u,v]-Fmaj[u,v]>0)and(p[v]=-1) then
            begin
              p[v]:=u;
              mmaj[v]:=min(mmaj[u], C[u,v]-Fmaj[u,v]);
              if v<>t then
                begin
                 q[q[0]]:=v;
                 inc(q[0]);
                end else
                begin
                m:=mmaj[t];
              exit;
              end;
            end;
          end;
        end;
        m:=0;
    end;
  begin
   assign(a,'maxflow.in');
   assign(b,'maxflow.out');
   reset(a);
   rewrite(b);
   Readln(a,k,n);
   for i:=1 to n do
    begin
     Readln(a,x,y,nk);
     C[x,y]:=nk;
     inc(E[x,0]);
     E[x,E[x,0]]:=y;
     inc(E[y,0]);
     E[y,E[y,0]]:=x;
    end;
    s:=1;
    t:=k;
   while true do
     begin
       BFS;
       if m=0 then
          break;
       f:=f+m;
       v:=t;
       while v<>s do
         begin
          u:=P[v];
          Fmaj[u,v]:=Fmaj[u,v]+m;
          Fmaj[v,u]:=Fmaj[v,u]-m;
          v:=u;
         end;

     end;
   Writeln(b,f);
   close(b);
  end.