// Author : hejinming2012
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define dbg(x) cout << #x " = " << (x) << endl
#define quickio ios::sync_with_stdio(false);
#define quickin cin.tie(0);
#define quickout cout.tie(0);

using namespace std;
inline int read() {
    int n = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { n = (n << 1) + (n << 3) + (c & 15); c = getchar(); }
    return n * f;
}
inline void write(int x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
struct NP {
	int u, p;
};
vector<NP> dfs(int r, const vector < vector < pair < int, int > > > &g) {
    vector < NP > po;
	stack < tuple < int, int, bool > > st;
    st.emplace(r, -1, false);
    while(!st.empty()) {
        auto [u, p, v] = st.top(); st.pop();
        if(v) po.emplace_back(NP{u, p});
        else {
            st.emplace(u, p, true);
            for(auto &[v, w] : g[u])
				if(v != p) st.emplace(v, u, false);
        }
    }
    return po;
}
signed main() {
    quickio
	quickin
	quickout
    int T = read();
    for(int _ = 1; _ <= T; _++) {
        int n = read(), k = read();
        vector < vector < pair < int, int > > > g(n + 1);
        for(int i = 1; i < n; i++) {
            int u = read(), v = read(), w = read();
            g[u].emplace_back(v, w);
            g[v].emplace_back(u, w);
        }
        vector<NP> po = dfs(1, g);
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, LLONG_MAX)), sum(n + 1, vector<int>(k + 1));
        for(auto &np : po) {
            int u = np.u, p = np.p;
            if(g[u].size() == 1 && u != 1) {
                dp[u][0] = dp[u][1] = sum[u][0] = sum[u][1] = 0;
                for(int i = 2; i <= k; i++)
					dp[u][i] = LLONG_MAX, sum[u][i] = 0;
            } else {
                vector<int> dp_c(k + 1, LLONG_MAX), sum_c(k + 1, 0);
                dp_c[0] = sum_c[0] = 0;
                for(auto &[v, w] : g[u]) {
                    if(v == p) continue;
                    vector<int> sum_ch(k + 1, 0);
                    for(int i = 0; i <= k; i++) {
                        if(dp[v][i] == LLONG_MAX && i != 0)
							sum_ch[i] = LLONG_MAX;
                        else sum_ch[i] = sum[v][i] + i * w;
                    }
                    vector <int> dp_ch(k + 1, LLONG_MAX);
                    for(int i = 0; i <= k; i++) dp_ch[i] = dp[v][i];
                    vector <int> temp_dp(k + 1, LLONG_MAX), temp_sum(k + 1, 0);
                    for(int i1 = 0; i1 <= k; i1++) {
                        if(dp_c[i1] == LLONG_MAX) continue;
                        for(int i2 = 0; i2 <= k - i1; i2++) {
                            if(dp_ch[i2] == LLONG_MAX) continue;
                            int new_m = i1 + i2;
                            if(new_m > k) continue;
                            if(sum_ch[i2] == LLONG_MAX) continue;
                            int tmp_sum = sum_c[i1] + sum_ch[i2];
                            int tmp_dp = dp_c[i1] + dp_ch[i2] + i1 * sum_ch[i2] + i2 * sum_c[i1];
							if(tmp_dp < temp_dp[new_m]) {
								temp_dp[new_m] = tmp_dp;
								temp_sum[new_m] = tmp_sum;
							}
                        }
                    }
                    dp_c = move(temp_dp);
                    sum_c = move(temp_sum);
                }
                for(int i = 0; i <= k; i++) {
					dp[u][i] = dp_c[i];
					sum[u][i] = sum_c[i];
				}
            }
        }
		printf("Case #%lld: %lld\n", _, dp[1][k]);
    }
}