#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=400005;
mt19937 rng(19260817);
int rnd(int l,int r){
    return rng()%(r-l+1)+l;
}
struct node{
    ll val,tag;
    int key,l,r,sz;
}tr[N];
int cnt=0,rt[N];
void pushup(int id){
    int ls=tr[id].l,rs=tr[id].r;
    tr[id].sz=tr[ls].sz+tr[rs].sz+1;
}
void pushtag(int id,ll k){
    tr[id].val+=k;tr[id].tag+=k;
}
void pushdown(int id){
    int ls=tr[id].l,rs=tr[id].r;
    ll k=tr[id].tag;tr[id].tag=0;
    pushtag(ls,k);pushtag(rs,k);
}
int newnode(ll val){
    ++cnt;
    tr[cnt].val=val;tr[cnt].tag=0;tr[cnt].l=tr[cnt].r=0;
    tr[cnt].key=rng();tr[cnt].sz=1;
    return cnt;
}
void splitsz(int cur,int siz,int &x,int &y){
    if(!cur){
        x=y=0;return;
    }
    pushdown(cur);
    if(tr[tr[cur].l].sz+1<=siz){
        x=cur;
        splitsz(tr[x].r,siz-tr[tr[cur].l].sz-1,tr[x].r,y);
    }
    else{
        y=cur;
        splitsz(tr[y].l,siz,x,tr[y].l);
    }
    pushup(cur);
}
void splitval(int cur,int val,int &x,int &y){
    if(!cur){
        x=y=0;return;
    }
    pushdown(cur);
    if(tr[cur].val>=val){
        x=cur;
        splitval(tr[x].r,val,tr[x].r,y);
    }
    else{
        y=cur;
        splitval(tr[y].l,val,x,tr[y].l);
    }
    pushup(cur);
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(tr[x].key<=tr[y].key){
        pushdown(x);
        tr[x].r=merge(tr[x].r,y);
        pushup(x);
        return x;
    }
    else{
        pushdown(y);
        tr[y].l=merge(x,tr[y].l);
        pushup(y);
        return y;
    }
}
void output(int u){
    if(!u)return;
    pushdown(u);
    output(tr[u].l);
    cout<<tr[u].val<<" ";
    output(tr[u].r);
}
int A,B,C;
void ins(int u,ll val){
    splitval(rt[u],val,A,B);
    rt[u]=merge(A,merge(newnode(val),B));
}
int n,k;
vector<pii>g[N];
void dfs(int u,int fa){
    for(auto pr:g[u]){
        int v=pr.fi;ll w=pr.se;
        if(v==fa)continue;
        dfs(v,u);
        if(tr[rt[v]].sz<=k/2){
            pushtag(rt[v],w);
        }
        else if(tr[rt[v]].sz==(k+1)/2){
            splitsz(rt[v],k/2,A,B);
            pushtag(A,w);
            rt[v]=merge(A,B);
        }
        else{
            splitsz(rt[v],(k+1)/2,A,C);
            splitsz(A,k/2,A,B);
            pushtag(A,w);pushtag(C,-w);
            rt[v]=merge(A,merge(B,C));
        }
        if(tr[u].sz<tr[v].sz)swap(rt[u],rt[v]);
        while(rt[v]){
            pushdown(rt[v]);
            ins(u,tr[rt[v]].val);
            rt[v]=merge(tr[rt[v]].l,tr[rt[v]].r);
        }
    }
    ins(u,0);
}
void solve(){
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int x,y,w;
        cin>>x>>y>>w;
        g[x].push_back({y,w});
        g[y].push_back({x,w});
    }
    dfs(1,0);
    splitsz(rt[1],k,A,C);
    ll ans=0;
    while(A){
        ans+=tr[A].val;
        pushdown(A);
        A=merge(tr[A].l,tr[A].r);
    }
    cout<<ans*2<<"\n";
    for(int i=1;i<=n;i++){
        g[i].clear();rt[i]=0;
    }
    for(int i=0;i<=cnt;i++){
        tr[i].key=tr[i].l=tr[i].r=tr[i].sz=tr[i].val=tr[i].tag=0;
    }
    cnt=0;A=B=C=0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve();
    return 0;
}