# include <stdio.h>
# include <algorithm>

using namespace std;

struct daw
{
    long long rg,lf,nd,vl,mx;
};

long long a,b;

long long w[409];
long long c[409][5];
long long v[409][409];

daw d[409];

void btr(long long x)
{
    if(d[x*2+1].vl!=0)
    btr(x*2+1);

    if(d[x*2+2].vl!=0)
    btr(x*2+2);

    if(x!=0)
    d[(x-1)/2].nd=d[(x-1)/2].nd+d[x].nd+1;
}

long long dp(long long x, long long y)
{
//    prlong longf("%d %d",x,y);getchar();

    if(y==0)
    return 0;

    if(v[x][y]>0)
    return v[x][y];

    for(long long i=0;i<=y;i++)
    if(d[x].nd-d[x*2+2].nd>=i && d[x*2+1].vl>0 && d[x*2+2].vl>0)
    {
        long long q=0;

        if(i!=0)
        q+=d[x].lf;

        if(i!=y)
        q+=d[x].rg;

        if(i==0)
        v[x][y]=max(v[x][y],dp(x*2+2,y-1)+q);

        else if(i==y)
        v[x][y]=max(v[x][y],dp(x*2+1,y-1)+q);

        else
        v[x][y]=max(v[x][y],dp(x*2+1,i-1)+dp(x*2+2,y-i-1)+q);
    }

    return v[x][y];
}

int main()
{
    scanf("%lld %lld",&a,&b);

    for(long long i=0;i<a-1;i++)
    scanf("%lld %lld %lld",&c[i][0],&c[i][1],&c[i][2]);

    d[0].vl=1;
    w[1]=1;

    for(long long i=0;i<a-1;i++)
    for(long long j=0;j<a-1;j++)
    {
        if(d[i].vl==c[j][0] && w[c[j][1]]==0)
        {
            if(d[i*2+1].vl==0)
            {d[i].lf=c[j][2];  d[i*2+1].vl=c[j][1];}

            else
            {d[i].rg=c[j][2];  d[i*2+2].vl=c[j][1];}

            w[c[j][0]]=1;
        }

        if(d[i].vl==c[j][1] && w[c[j][0]]==0)
        {
            if(d[i*2+1].vl==0)
            {d[i].lf=c[j][2];  d[i*2+1].vl=c[j][0];}

            else
            {d[i].rg=c[j][2];  d[i*2+2].vl=c[j][0];}

            w[c[j][0]]=1;
        }
    }

    btr(0);

    if(b==1)
    {printf("%lld",max(d[0].rg,d[0].lf));return 0;}

    printf("%lld",dp(0,b));

    getchar();
    getchar();
}


Thanks