/*
[HAOI2015]树上染色  的弱化版 
*/ 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m,cas;
int main(){
    for(scanf("%d",&T);T--;){
        scanf("%d%d",&n,&m);
        vector<vector<pair<int,ll> > >e(n+1);
        for(int i=1,x,y,z;i<n;i++){
            scanf("%d%d%d",&x,&y,&z);
            e[x].emplace_back(y,z);
            e[y].emplace_back(x,z);
        }
        if(m==1){printf("Case #%d: 0\n",++cas);continue;}
        if(n==2){printf("Case #%d: %lld\n",++cas,e[1][0].second);continue;}
        vector<vector<ll> > f(n+1,vector<ll>(m+1,1e14));vector<int>siz(n+1,0);
        function<void(int,int)>dfs=[&](int u,int fa)->void{
            bool leaf=1;
            f[u][0]=0;
            for(auto t:e[u]){
                int v=t.first;ll w=t.second;
                if(v==fa) continue;
                leaf=0;
                dfs(v,u);
                for(int i=min(siz[u],m);~i;i--){
                    for(int j=min(siz[v],m-i);~j;j--){
                        f[u][i+j]=min(f[u][i+j],f[u][i]+f[v][j]+w*(m-j)*j);
                    }
                }
                siz[u]+=siz[v];
            }
            if(leaf){f[u][1]=0;siz[u]=1;}
        };
        int rt=0;
        for(int i=1;i<=n;i++) if(e[i].size()>1){rt=i;break;}
        dfs(rt,0);
        printf("Case #%d: %lld\n",++cas,f[rt][m]);
    }
    return 0;
}