riverse

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int MOD = 2000000001;
const int maxN = 100;



int main() {
    int N, K;
    scanf("%d %d", &N, &K);
    vector<pair<int,int> > edge[maxN+1];
    int outdeg[maxN+1] = {0};
    int nodeVal[maxN+1] = {0};
    int parent[maxN+1] = {0};
    
    // dp[x][k][1] : minimum cost of transportation of moving all the logs in subtree rooted at node x to node x. 1 means node x has a sawmill
    // dp[x][k][0] : same but node x does not have a saw mill.
    long long dp[maxN+1][maxN+1][2] = {0};
    
    // accum[x][k][0]: the # of all the logs (in subtree rooted at node x) remaining at node x after transportation. 0 means node x has a sawmil.
    // accum[x][k][1]: same but node x does not have a sawmill.
    int accum[maxN+1][maxN+1][2] = {0};

    // initializing...
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            for (int k = 0; k < 2; k++) {
                dp[i][j][k] = 2000000001;
                accum[i][j][k] = 2000000001;
            }
        }
    }

    // construct the graph
    nodeVal[0] = 0;
    for (int i = 1; i <= N; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        nodeVal[i] = a;
        edge[b].push_back(make_pair(i, c));
        outdeg[b]++;
        parent[i] = b;
    }

    queue<int> q;
    vector<int> top;

    for (int i = 1; i <= N; i++) {
        // pick out leaf nodes
        if (outdeg[i] == 0) {
            q.push(i);
        }
    }

    // topological sort
    while (!q.empty()) {
        int node = q.front(); q.pop();
        top.push_back(node);
        if (node > 0 && --outdeg[parent[node]] == 0) {
            q.push(parent[node]);
        }
    }

    // conisder bottom up..
    for (int i = 0; i < top.size(); i++) {

        int node = top[i];
        dp[node][0][0] = dp[node][1][1] = 0;
        accum[node][0][0] = nodeVal[node];
        accum[node][1][1] = 0;

        // doing tree dp..
        for (int j = 0; j < edge[node].size(); j++) {
            int child = edge[node][j].first;
            int edgeCost = edge[node][j].second;

            for (int k = K; k >= 0; k--) {
                long long res0 = 2000000001;
                long long res1 = 2000000001;
                int accum0 = 2000000001;

                for (int m = 0; m <= k; m++) {

                    // if node does not have a sawmill...
                    // and nth child has m saw mills in its subtree
                    // then, you have to move sawmills from child to node. with the cost as edgeCost*accum[child][m][0]
                    // remember, accum[child][m][0] has remaining sawmills moved to node child.
                    if (dp[node][k-m][0] + dp[child][m][0] + edgeCost*accum[child][m][0] < res0) {
                        res0 = dp[node][k-m][0] + dp[child][m][0] + edgeCost*accum[child][m][0];
                        
                        // sawmills moved up from child to node + whatever logs node has
                        accum0 = accum[child][m][0] + nodeVal[node];
                    }

                    // similar case as above
                    // but the child has a sawmill, so no additional logs to move up
                    // just add up the cost
                    if (dp[node][k-m][0] + dp[child][m][1] < res0) {
                        res0 = dp[node][k-m][0] + dp[child][m][1];
                        accum0 = nodeVal[node];
                    }
                    
                    // if node has a sawmil and its child has a sawmill,
                    // there should be no logs remaining at node
                    if (dp[node][k-m][1] + dp[child][m][1] < res1) {
                        res1 = dp[node][k-m][1] + dp[child][m][1];
                    }

                    // if node as a sawmill but its child does not
                    // move up the logs and add the cost of transportation but no logs remaining at node
                    if (dp[node][k-m][1] + dp[child][m][0] + edgeCost*accum[child][m][0] < res1) {
                        res1 = dp[node][k-m][1] + dp[child][m][0] + edgeCost*accum[child][m][0];
                    }
                }

                // update
                dp[node][k][0] = res0;
                accum[node][k][0] = accum0;
                dp[node][k][1] = res1;
                accum[node][k][1] = 0;

            }
        }
    }
    
    // answer
    printf("%lld\n", dp[0][K][0]);
}