/*
Sprendimo autorius - Vytis Banaitis
Patogumo dėlei, tarkime, kad Baittaunas yra kaimas, kurio numeris yra nulis.
Tarkime, kad kaimo grupė yra visi kaimai, iš kurių malkos praplaukia pro šį kaimą 
(kaimas įeina į savo grupę). Reikia apskaičiuoti mažiausią kainą A(v,t,l) malkoms plukdyti 
iš kiekvieno kaimo v grupės, kiekvienam lentpjūvių, toje grupėje, kiekiui t, kiekvienam kaimui
l, esančiam pasroviui nuo v, į kurį būtų plukdomos visos malkos neperdirbtos v grupėje.
Apskaičiavus, A(0,k,0) yra atsakymas.
*/
#include <cstdlib>
#include <cstdio>

using namespace std;

int n, k;
int w[201], v[201], d[201];
int c[201][2];
int A[201][51][201];

void input()
{
    v[0] = -1;
    scanf("%d%d",&n,&k);
    int m = n+1;
    for (int i=1;i<=n;i++) {
        scanf("%d%d%d",&w[i],&v[i],&d[i]);
        int p = v[i];
        while (c[p][0]) p = c[p][1];
        v[i] = p;
        c[p][0] = i;
        c[p][1] = m;
        v[m++] = p;
    }
    n = m;
}

void calc(int i, int nn)
{
    int a;
    for (int t=0;t<=k;t++) for (int l=0,ll=0,p=i;p>=0;l++,ll+=d[p],p=v[p]) {
        if (t >= nn) { A[i][t][l] = 0; continue; }
        if (nn == 1) { A[i][t][l] = w[i]*ll; continue; }
        a = A[c[i][0]][0][l+1] + A[c[i][1]][t][l+1];
        for (int tt=1;tt<=t;tt++) a <?= A[c[i][0]][tt][l+1] + A[c[i][1]][t-tt][l+1];
        A[i][t][l] = a + w[i]*ll;
        if (!t) continue;
        a = A[c[i][0]][0][1] + A[c[i][1]][t-1][1];
        for (int tt=1;tt<t;tt++) a <?= A[c[i][0]][tt][1] + A[c[i][1]][t-1-tt][1];
        A[i][t][l] <?= a;
    }
}

int search(int i)
{
    int a = 0;
    if (c[i][0]) {
        a = search(c[i][0]);
        a += search(c[i][1]);
    }
    calc(i,++a);
    return a;
}

int main()
{
    input();
    search(0);
    printf("%d\n",A[0][k][0]);
    return 0;
}