program ti;
var n,l1,l2,q,j:longint;
    pp:array[1..100]of boolean;
    a:array[1..100,1..3]of longint;
    could:array[1..100,0..100]of longint;

function choose(now,k:longint):longint;
begin
     if a[now,1]=k then choose:=a[now,2]
        else choose:=a[now,1];
end;

procedure done(n1:longint;var n2:longint);
begin
     if n1>n2 then n2:=n1;
end;

function pd(n1,n2:longint):boolean;
begin
     if n1=n2 then pd:=true
        else pd:=false;
end;

procedure cl(now:longint);
var p1,p2,i,l1,l2:longint;
begin
     p1:=0; p2:=0; l1:=0; l2:=0;
     for i:=1 to n-1 do if (pp[i])and((pd(a[i,1],now))or(pd(a
[i,2],now))) then
         if p1=0 then begin
            p1:=choose(i,now);
            pp[i]:=false;
            cl(p1);
            l1:=a[i,3];
         end else begin
             p2:=choose(i,now);
             pp[i]:=false;
             cl(p2);
             l2:=a[i,3];
             break;
         end;
     for i:=1 to q do could[now,i]:=-1;
     could[now,0]:=0;
     i:=0;
     while (i+1<=q)and(could[p1,i]<>-1) do begin
           j:=0;
           while (j+i+1<=q)and(could[p2,j]<>-1) do begin
                 if (i+j+2<=q)and(p1<>0)and(p2<>0) then done(could
[p1,i]+could[p2,j]+l1+l2,could[now,i+j+2]);
                 if (i=0)and(p2<>0) then done(could[p2,j]+l2,could
[now,j+1]);
                 if (j=0)and(p1<>0) then done(could[p1,i]+l1,could
[now,i+1]);
                 j:=j+1;
           end;
           i:=i+1;
     end;
end;

procedure read_data;
var i:longint;
begin
     readln(n,q);
     for i:=1 to n-1 do readln(a[i,1],a[i,2],a[i,3]);
     fillchar(pp,sizeof(pp),true);
     cl(1);
end;

procedure write_data;
begin
     write(could[1,q]);
end;

begin
     read_data;
     write_data;
end.