#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int maxn = 1e2 + ;

int Lchild[maxn], Rchild[maxn], dp[maxn][maxn][maxn];

int a[maxn], fa[maxn], len[maxn];

int dfs(int cur, int hasPoint, int k, int dis) {

    if (cur == - || hasPoint == -) return ;

    if (dp[cur][hasPoint][k] != inf) return dp[cur][hasPoint][k];

    int &now = dp[cur][hasPoint][k]; //引用改值

    for (int i = ; i <= k; ++i) { //这个cur节点不做中转站。

        now = min(now, dfs(Lchild[cur], hasPoint, i, dis + len[cur]) + dfs(Rchild[cur], hasPoint, k - i, dis) + a[cur] * (dis + len[cur]));

    }

    for (int i = ; i < k; ++i) { // 这个点用来中转

        now = min(now, dfs(Lchild[cur], cur, i, ) + dfs(Rchild[cur], hasPoint, k - i - , dis));

    }

    return dp[cur][hasPoint][k];

}

void work() {

    int n, k;

    cin >> n >> k;

    memset(dp, 0x3f, sizeof dp);

    memset(Lchild, -, sizeof Lchild);

    memset(Rchild, -, sizeof Rchild);

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

        cin >> a[i] >> fa[i] >> len[i];

        Rchild[i] = Lchild[fa[i]];

        Lchild[fa[i]] = i;

    }

    cout << dfs(, , k, ) << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}