var
  map:array[1..1000,1..1000] of longint;
  g:array[1..1000,0..1000] of longint;
  i,m,n,x,y,z,max:longint;
  s,h,v:array[0..1000] of longint;
function min(x,y:longint):longint;
begin
  if x<y then min:=x
         else min:=y;
end;
function dfs(x,sum:longint):longint;
var
  i,j,k,minh:longint;
begin
  if x=n then exit(sum);
  minh:=n+1;
  for j:=1 to g[x,0] do
  begin
    i:=g[x,s[x]];
    if (map[x,i]>0)
       then begin
              if h[x]=h[i]+1
                 then begin
                         k:=dfs(i,min(sum,map[x,i]));
                         if h[1]>n then exit(0);
                         if k>0
                            then begin
                                   dec(map[x,i],k);
                                   inc(map[i,x],k);
                                   exit(k);
                                 end;
              if h[1]>n then exit(0);
            end;
      minh:=min(minh,h[i]);
      if h[1]>n then exit(0);
    end;
    inc(s[x]);
    if s[x]>g[x,0] then s[x]:=1;
  end;
  dec(v[h[x]]);
  if v[h[x]]=0 then h[1]:=n+1;
  h[x]:=minh+1;
  inc(v[h[x]]);
  exit(0);
end;
begin
  readln(m,n);
  for i:=1 to n do
    s[i]:=1;
  for i:=1 to m do
  begin
    readln(x,y,z);
    if (map[x,y]=0) and (map[y,x]=0)
      then begin
             inc(g[x,0]);g[x,g[x,0]]:=y;
             inc(g[y,0]);g[y,g[y,0]]:=x;
          end;
    inc(map[x,y],z);
  end;
  max:=0;
  fillchar(h,sizeof(h),0);
  fillchar(v,sizeof(v),0);
  while h[1]<=n do
   inc(max,dfs(1,20000000));
  writeln(max);
end.