#include<cstdio>

#include<iostream>

#include<cmath>

#include<cstring>

#include<algorithm>

#define maxn 105

#define inf 1061109567

using namespace std;

char ch;

int n,k,a,b,c,tot,w[maxn],now[maxn],son[maxn],pre[maxn],val[maxn];

int dist[maxn],f[maxn][maxn][maxn],tmp[maxn][maxn][maxn];

bool ok,bo[maxn][maxn];

void read(int &x){

    for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;

    for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());

    if (ok) x=-x;

}

void put(int a,int b,int c){pre[++tot]=now[a],now[a]=tot,son[tot]=b,val[tot]=c;}

int turn(int x){if (x==inf) return ;return x;}

void dfs(int u,int last){

    if (bo[u][last]) return;

    bo[u][last]=;

    for (int p=now[u],v=son[p];p;p=pre[p],v=son[p]){

        dist[v]=dist[u]+val[p];

        dfs(v,last),dfs(v,v);

        for (int i=;i<=k;i++){

            f[u][last][i]=inf;

            for (int j=;j<=i;j++){

                if (i>j) f[u][last][i]=min(f[u][last][i],tmp[u][last][i-j-]+f[v][v][j]);

                f[u][last][i]=min(f[u][last][i],tmp[u][last][i-j]+f[v][last][j]+w[v]*(dist[v]-dist[last]));

            }

        }

        memcpy(tmp[u][last],f[u][last],sizeof(tmp[u][last]));

    }

}

int main(){

    read(n),read(k);

    for (int i=;i<=n;i++) read(w[i]),read(b),read(c),put(b,i,c);

    dfs(,);

    printf("%d\n",f[][][k]);

    return ;

}