// Skyqwq
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> void inline read(T &x) {
    x = 0; int f = 1; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') { f = -1; } s = getchar(); }
    while (s >= '0' && s <= '9') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

template <typename T> bool inline chkMin(T &x, T y) { return y < x ? x = y, 1 : 0; }
template <typename T> bool inline chkMax(T &x, T y) { return y > x ? x = y, 1 : 0; }

const int N = 4e4 + 5, INF = -1e9, S = 100000005, M = 5e5 + 5;

vector<int> g[N];

int n, m, fa[N], a[N], w[N], pre[N], dfn[N], dfncnt, sz[N], s[N], idx, loc[N], vp[N], dy[N], pool[S];

int Z;

int& F(int x, int y) {
    if (!y) return Z;
    if (x > idx) return Z;
    return pool[(x - 1) * m + y];
}

int& H(int x, int y) {
    if (!y) return Z;
    if (x > idx) return Z;
    return pool[(x - 1) * m + y + idx * m];
}

void inline clr() {
    for (int i = 0; i <= idx + 1; i++) {
        g[i].clear();
        dfn[i] = pre[i] = sz[i] = 0;
    }
    dfncnt = idx = 0;
}

void dfs(int u) {
    dfn[u] = ++dfncnt, pre[dfn[u]] = u; sz[u] = 1;
    for (int v: g[u]) {
        dfs(v);
        sz[u] += sz[v];
    }
}

int q[M];

void upd(int z, int t, int w) {
    int hh = 0, tt = 0;
    q[0] = 0;
    for (int i = 1; i <= m; i++) {
        while (hh <= tt && q[hh] < i - t) hh++;
        if (hh <= tt) {
            int j = q[hh];
            chkMax(F(z, i), F(z + 1, j) + (i - j) * w);
        }
        while (hh <= tt && F(z + 1, q[tt]) - q[tt] * w < F(z + 1, i) - i * w) tt--;
        q[++tt] = i;
    }
}

void inline sv() {
    for (int i = idx; i; i--) {
        int u = pre[i], v = i + sz[u];
        int W = min(a[u], m);
        upd(i, W, w[u]);
        for (int j = 0; j <= m; j++) chkMax(F(i, j), F(v, j));
    }
}

void wk() {
    dfs(1);
    for (int i = 1; i <= idx + 1; i++) for (int j = 0; j <= m; j++) F(i, j) = 0;
    sv(); 
    for (int i = 1; i <= n; i++) loc[i] = dfn[i];
    dfncnt = 0;
    for (int i = 1; i <= idx + 1; i++) reverse(g[i].begin(), g[i].end());
    dfs(1);
    for (int i = 1; i <= idx + 1; i++) for (int j = 0; j <= m; j++) H(i, j) = F(i, j), F(i, j) = 0;
    sv();
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (vp[i]) assert(dy[i] == pre[dfn[i] + sz[i] - vp[i]]);
            int w = H(loc[i] + sz[i], j) + F(dfn[i] + sz[i] - vp[i], m - j) + s[i];
            chkMax(ans, w);
        }
    }
    printf("%d\n", ans);
}

int main() {
    int T; read(T);
    while (T--) {
        read(n), read(m); idx = n;
        for (int i = 1; i <= n; i++) {
            read(fa[i]), read(a[i]), read(w[i]), s[i] = s[fa[i]] + w[i];
            g[fa[i]].pb(i);
            vp[i] = 0; dy[i] = 0;
            if (a[i] > 1) {
                vp[i] = 1;
                ++idx;
                a[idx] = a[i] - 1;
                w[idx] = w[i], fa[idx] = i;
                g[i].pb(idx);
                dy[i] = idx;
                a[i] = 1;
            }
        }
        wk(); clr();
    }
    return 0;
}