#include <bits/stdc++.h>
using namespace std;

#define     F       first
#define     S       second
typedef pair<int, int>  pi;
typedef long long       ll;

const int MAX=1e5+9;
const ll OO=1e18+18;
int n, k, cntLeafs[MAX];
ll dp[MAX][109], temp[109];
vector<pi> adj[MAX];

template<typename T>
void Min(T& a, T b) {
    a=min(a, b);
}

void DFS(int cur, int par) {
    dp[cur][0]=0;
    for (int i=1; i<=k; ++i) {
        dp[cur][i]=OO;
    }

    if (adj[cur].size()==1) {
        dp[cur][1]=0;
        cntLeafs[cur]=1;
    }
    else {
        cntLeafs[cur]=0;
    }

    for (int i=0; i<adj[cur].size(); ++i) {
        int child=adj[cur][i].F,
            cost=adj[cur][i].S;

        if (child==par) {
            continue;
        }

        DFS(child, cur);
        cntLeafs[cur]+=cntLeafs[child];

        for (int i=0; i<=min(cntLeafs[cur], k); ++i) {
            temp[i]=OO;
        }

        for (int i=0; i<=min(cntLeafs[child], k); ++i) {
            for (int j=0; j<=cntLeafs[cur] && i+j<=k; ++j) {
                Min(temp[i+j], dp[child][i]+1LL*(k-i)*i*cost+dp[cur][j]);
            }
        }

        for (int i=0; i<=min(cntLeafs[cur], k); ++i) {
            Min(dp[cur][i], temp[i]);
        }
    }
}

int main() {
    int t;
    scanf("%d", &t);
    for (int testCase=1; testCase<=t; ++testCase) {
        scanf("%d%d", &n, &k);
        for (int i=1; i<=n; ++i) {
            adj[i].clear();
        }

        for (int i=1; i<=n-1; ++i) {
            int x, y, w;
            scanf("%d%d%d", &x, &y, &w);
            adj[x].push_back({y, w});
            adj[y].push_back({x, w});
        }

        if (n==2) {
            printf("Case #%d: %d\n", testCase, adj[1][0].S);
        }
        else {
            for (int i=1; i<=n; ++i) {
                if (adj[i].size()!=1) {
                    DFS(i, -1);
                    printf("Case #%d: %lld\n", testCase, dp[i][k]);
                    break;
                }
            }
        }
    }

    return 0;
}