var n,m,i,j,k,h,t,x,y,z,ans:longint;

  a:array[..,..]of longint;

  q,l:array[..]of longint;

function dfs(now,p:longint):longint;

var i,ll:longint;

begin

  if now=n then exit(p);

  for i:= to n do

    if(l[now]+=l[i])and(a[now,i]>)then begin

      if a[now,i]>p then ll:=dfs(i,p)

      else ll:=dfs(i,a[now,i]);

      a[now,i]:=a[now,i]-ll; a[i,now]:=a[i,now]+ll;

      if ll> then exit(ll);

    end;

  exit();

end;

begin

  read(m,n);

  for i:= to m do begin

    read(x,y,z);

    a[x,y]:=a[x,y]+z;

  end;

  ans:=;

  while true do begin

    for i:= to n do

      l[i]:=;

    h:=; t:=; q[]:=; l[]:=;

    repeat

      for i:= to n do

        if(l[i]=)and(a[q[h],i]>)then begin

          inc(t); q[t]:=i; l[i]:=l[q[h]]+;

        end;

      inc(h);

    until h>t;

    if l[n]= then break;

    repeat

      k:=dfs(,maxint);

      ans:=ans+k;

    until k=;

  end;

  writeln(ans);

end.