#include <iostream>#include <cstdio>using namespace std;typedef long long LL;const double EPS = 1e-6;const int INF = 0x3fffffff;const LL LINF = INF * 1ll * INF;using namespace std;#define MAXN 5005int head[MAXN],nxt[MAXN],e[MAXN],w[MAXN];int cnt;LL dp[MAXN][55];//适用于正负整数template <class T>inline bool scan_d(T &ret) {   char c; int sgn;   if(c=getchar(),c==EOF) return 0; //EOF   while(c!=‘-‘&&(c<‘0‘||c>‘9‘)) c=getchar();   sgn=(c==‘-‘)?-1:1;   ret=(c==‘-‘)?0:(c-‘0‘);   while(c=getchar(),c>=‘0‘&&c<=‘9‘) ret=ret*10+(c-‘0‘);   ret*=sgn;   return 1;}void addEdge(int u,int v,int w){    e[cnt] = v;    ::w[cnt] = w;    int tmp = head[u];    head[u] = cnt;    nxt[cnt++] = tmp;}int n,k;void update(LL &ans,LL v){    if(ans>v) ans = v;}void dfs(int u,int fa){    for(int i = head[u];~i;i = nxt[i]){        if(e[i]==fa) continue;        dfs(e[i],u);    }    for(int i = 0;i<=k;i++) dp[u][i] = LINF;    dp[u][1] = 0;    for(int i = head[u];~i;i = nxt[i]){        if(e[i]==fa) continue;        int v = e[i];        for(int a = k;a>=0;a--){            for(int b = 1;a+b<=k;b++){                if(dp[v][b]==LINF) break;                update(dp[u][a+b],dp[u][a]+dp[v][b]+2ll*b*(k-b)*w[i]);            }        }    }}int main(void){#ifndef ONLINE_JUDGE//    freopen("/Users/mac/Desktop/data.in","r",stdin);#endif    int t;    scanf("%d",&t);    while(t--){        //scanf("%d %d",&n,&k);        scan_d(n);        scan_d(k);        for(int i = 1;i<=n;i++) head[i] = -1;        cnt = 0;        for(int i = 0;i<n-1;i++){            int u,v,w;            scan_d(u);            scan_d(v);            scan_d(w);            addEdge(u,v,w);            addEdge(v,u,w);        }        LL ans = LINF;        dfs(1,-1);        for(int i = 1;i<=n;i++){            update(ans,dp[i][k]);        }        printf("%I64d\n",ans);    }    return 0;}