#include<time.h>
#include<random>
#include<cstdio>
#define MAX 200005
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
typedef long long ll;
using namespace std;
mt19937 rnd(time(0));
int T,n,k;
int head[MAX],s[MAX<<1],nxt[MAX<<1],val[MAX<<1];

int tot,pos[MAX],siz[MAX];
ll w[MAX],tag[MAX];
int son[MAX][2];
void down(int x)
{
    if(tag[x])
    {
        w[x]+=tag[x];
        if(son[x][0])tag[son[x][0]]+=tag[x];
        if(son[x][1])tag[son[x][1]]+=tag[x];
        tag[x]=0;
    }
}
void pus(int x)
{
    siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;
}
int build(int x)
{
    w[++tot]=x,siz[tot]=1,pos[tot]=rnd();
    tag[tot]=son[tot][0]=son[tot][1]=0;
    return tot;
}
void split(int i,int k,int&x,int&y)
{
    if(!i)
    {
        x=y=0;
        return;
    }
    down(i);
    if(siz[son[i][0]]<k)
    x=i,split(son[i][1],k-siz[son[i][0]]-1,son[i][1],y);
    else
    y=i,split(son[i][0],k,x,son[i][0]);
    pus(i);
}
void splitv(int i,int v,int&x,int&y)
{
    if(!i)
    {
        x=y=0;
        return;
    }
    down(i);
    if(val[i]<=k)
    x=i,split(son[i][1],k-siz[son[i][0]]-1,son[i][1],y);
    else
    y=i,split(son[i][0],k,x,son[i][0]);
    pus(i);
}
int merge(int x,int y)
{
    if(!x||!y)return x|y;
    down(x);down(y);
    if(pos[x]>pos[y])x^=y^=x^=y;
    int a,b;
    splitv(y,val[x],a,b);
    son[x][0]=merge(son[x][0],a);
    son[x][1]=merge(son[x][1],b);
    pus(x);
    return x;
}
void change(int i,int l,ll v)
{
    if(l>=siz[i])tag[i]+=v;
    else if(siz[son[i][0]]>l)change(son[i][0],l,v);
    else
    {
        tag[son[i][0]]+=v,l-=siz[son[i][0]];
        if(l)
        {
            w[i]+=v,--l;
            if(l)change(son[i][1],l,v);
        }
    }
}
void print(int i)
{
    down(i);
    if(son[i][0])print(son[i][0]);
    printf("%d ",w[i]);
    if(son[i][1])print(son[i][1]);
}
int _;
int dfs(int x,int fa)
{
    int rt=0;
    for(int i=head[x];i;i=nxt[i])
    if(s[i]!=fa)
    {
        int v=dfs(s[i],x);
        change(v,k>>1,val[i]);
        change(v,k+1>>1,val[i]);
        change(v,k,-val[i]);
        merge(v,rt);
    }
    if(siz[rt]>k)split(rt,k,rt,_);
    else if(siz[rt]<k)merge(rt,build(0));
    return rt;
}
ll findans(int i)
{
    down(i);
    ll ans=w[i];
    if(son[i][0])ans+=findans(son[i][0]);
    if(son[i][1])ans+=findans(son[i][1]);
    return ans;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        //clear
        tot=0;
        for(int i=1;i<=n;++i)head[i]=0;
        scanf("%d%d",&n,&k);
        for(int i=1;i<n;++i)
        {
            int x,y,v;
            scanf("%d%d%d",&x,&y,&v);
            s[i]=y;nxt[i]=head[x];head[x]=i;
            s[i+n-1]=x;nxt[i+n-1]=head[y];head[y]=i+n-1;
            val[i]=val[i+n-1]=v;
        }
        int rt=dfs(1,-1);
        printf("%lld\n",findans(rt)*2);
    }
}