#include<bits/stdc++.h>
using namespace std;
int a[105],minn=0x3f3f3f3f3f3f,vis[105]={1},w[105],fa[105],d[105],n,k;
int find(int x){
	int ans=0,nxt=x;
	while(vis[nxt]==0){
		ans+=d[nxt];
		nxt=fa[nxt];
	}
	return ans*w[x];
}
bool check(){
	int ans=0;
	for(int i=1;i<=n;i++){
		if(vis[i]==0)ans+=find(i);
		if(ans>=minn) return 0;
	}
	if(minn>=ans){
		minn=ans;
		return 1;
	}
	return 0;
}
void FA(){
    int i=0;
	while((double)clock()/CLOCKS_PER_SEC<0.94){
	    i++;
		int l=rand()%k+1,r=rand()%n+1;
		while(vis[r]==1){
			r=(r+rand()%30)%n+1;
		}
		vis[a[l]]=0;
		vis[r]=1;
		if(check()==0){
			if((double)clock()/CLOCKS_PER_SEC<0.5){
				vis[r]=0;
				vis[a[l]]=1;				
			}
			else {
				a[l]=r;
			}
		}
		else {
			a[l]=r;
		}
	}
}
int main(){
	srand(time(0));
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>fa[i]>>d[i];
	}
	for(int i=1;i<=k;i++){
		vis[i]=1;
		a[i]=i;
	}
	FA();
	cout<<minn;
	return 0;
}