#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int N=2e5+10;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}

int T,n,k;
int tot,head[N],ver[N<<1],e[N<<1],ne[N<<1];

struct Heap
{
    priority_queue<ll,vector<ll>,greater<ll> >h1,h2;
    ll v,tag1,tag2;
    Heap() : v(-1),tag1(0),tag2(0){}
    int size(){return h1.size()+h2.size()+(v!=-1);}
    void add(ll val)
    {
        if(h1.size()<k/2)return h1.push(val-tag1);
        if(val>h1.top()+tag1)
        {
            ll ne=h1.top()+tag1;
            return h1.pop(),h1.push(val-tag1),add(ne);
        }
        if((k&1)&&v==-1)return v=val,void();
        if((k&1)&&val>v)
        {
            ll ne=v;
            return v=val,add(ne);
        }
        if(h2.size()<k/2)return h2.push(val-tag2);
        if(val>h2.top()+tag2)h2.pop(),h2.push(val-tag2);
    }
}f[N];

inline void add(int u,int v,int w)
{
    ver[++tot]=v;
    e[tot]=w;
    ne[tot]=head[u];
    head[u]=tot;
}
inline void init()
{
    tot=0;
    memset(head,0,sizeof(head));
}
inline void merge(Heap &x,Heap &y)
{
    if(x.size()<y.size())swap(x,y);
    while(!y.h1.empty())x.add(y.h1.top()+y.tag1),y.h1.pop();
    while(!y.h2.empty())x.add(y.h2.top()+y.tag2),y.h2.pop();
    if(~y.v)x.add(y.v),y.v=-1;
}
void dfs(int x,int fa)
{
    f[x].add(0);
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        dfs(y,x);
        f[y].tag1+=e[i]<<1,f[y].tag2-=e[i]<<1;
        merge(f[x],f[y]);
    }
}
inline void solve()
{
    init();
    read(n,k);
    for(int i=1,u,v,w;i<n;i++)read(u,v,w),add(u,v,w),add(v,u,w);
    dfs(1,0);
    ll ans=0;
    while(!f[1].h1.empty())ans+=f[1].h1.top(),f[1].h1.pop();
    while(!f[1].h2.empty())ans+=f[1].h2.top(),f[1].h2.pop();
    if((k&1)&&(~f[1].v))ans+=f[1].v,f[1].v=-1;
    printf("%lld",ans);
}
int main()
{
    // freopen("2.in","r",stdin);
    read(T);
    // T=1;
    while(T--)solve();
    return 0;
}