#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
const int maxn=200010;
il int read(){
    int x=0;
    char c=getchar();
    for(;!(c>='0'&&c<='9');c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
struct edge{
    int v,w,to;
}e[maxn<<1];
int head[maxn],ecnt;
void addedge(int u,int v,int w){
    e[++ecnt].v=v,e[ecnt].w=w;
    e[ecnt].to=head[u],head[u]=ecnt;
}
ll pre[maxn];
int n,k,T,a[maxn],cnt;
bool vis[maxn];
void dfs(int fa,int x,int lw=0){
    if(vis[x]&&fa) return ;
    pre[x]=pre[fa]+lw;
    for(int i=head[x];i;i=e[i].to)
        if(e[i].v^fa) dfs(x,e[i].v,e[i].w);
}
int ldis(int x){
    for(int i=1;i<=n;i++) pre[i]=0;
    dfs(0,x);
    ll Mx=0,id;
    for(int i=1;i<=n;i++)
        if(pre[i]>Mx) Mx=pre[i],id=i;
    return id;
}
int main(){
    T=read();
    while(T--){
        for(int i=1;i<=n;i++) head[i]=vis[i]=0; ecnt=cnt=0;
        n=read(),k=read();
        for(int i=1;i<n;i++){
            int x=read(),y=read(),z=read();
            addedge(x,y,z),addedge(y,x,z);
        }
        ll sum=0;
        a[1]=ldis(1),vis[a[1]]=1;
        for(int i=2;i<=k;i++)
            a[i]=ldis(a[i-1]),vis[a[i]]=1,sum+=pre[a[i]];
        for(int i=1;i<=n;i++) pre[i]=vis[i]=0;
        dfs(0,a[1]),sum+=pre[a[k]];
        printf("%lld\n",sum);
    }
    return 0;
}