#include <bits/stdc++.h>

using namespace std;
using ll=long long;

constexpr int MAXN=4e5+10;

struct Node {
    int son[2],fa,siz;
    ll val,sum,tag;
    Node() {memset(son,0,sizeof(son)); fa=val=sum=siz=tag=0;}
};

struct Splay {
    Node t[MAXN<<1]; int stk[MAXN<<1],tot,top,rt[MAXN];
    Splay() {tot=top=0; t[0]=Node(); memset(rt,0,sizeof(rt));}
    int create(ll val=0) {
        int p=top?stk[top--]:++tot;
        t[p]=Node(); t[p].siz=1; t[p].val=t[p].sum=val; return p;
    }
    void drop(int x) {stk[++top]=x;}
    void clear(int n) {
        tot=top=0; memset(rt,0,sizeof(int)*(n+1));
    }
    bool isroot(int x) {return !t[x].fa;}
    bool getpos(int x) {return t[t[x].fa].son[1]==x;}
    void pushup(int x) {
        int ls=t[x].son[0],rs=t[x].son[1]; t[x].sum=t[x].val; t[x].siz=1;
        if(ls) t[x].sum+=t[ls].sum,t[x].siz+=t[ls].siz;
        if(rs) t[x].sum+=t[rs].sum,t[x].siz+=t[rs].siz;
    }
    void add(int x,ll v) {
        t[x].sum+=1ll*t[x].siz*v,t[x].val+=v,t[x].tag+=v;
    }
    void pushdown(int x) {
        int ls=t[x].son[0],rs=t[x].son[1];
        if(t[x].tag) {
            if(ls) add(ls,t[x].tag);
            if(rs) add(rs,t[x].tag);
            t[x].tag=0;
        }
    }
    void rotate(int x) {
        int y=t[x].fa,z=t[y].fa,p=getpos(x);
        if(!isroot(y)) t[z].son[getpos(y)]=x;
        t[x].fa=z; t[y].son[p]=t[x].son[p^1]; t[t[x].son[p^1]].fa=y;
        t[y].fa=x; t[x].son[p^1]=y; pushup(y); pushup(x);
    }
    void splay(int id,int x,int to=0) {
        for(int fa;fa=t[x].fa,!isroot(x);rotate(x)) if(!isroot(fa)) rotate(getpos(x)==getpos(fa)?fa:x);
        if(!to) rt[id]=x;
    }
    void insert(int id,ll v) {
        if(!rt[id]) {rt[id]=create(v); return;}
        int p=0,x=rt[id];
        while(x) pushdown(x),p=x,x=t[x].son[v<t[x].val];
        x=create(v); t[x].fa=p; t[p].son[v<t[p].val]=x; pushup(p); splay(id,x);
    }
    int findByOrder(int id,int ord) {
        assert(ord<=t[rt[id]].siz);  pushdown(rt[id]);
        for(int x=rt[id],ls,rs;ls=t[x].son[0],rs=t[x].son[1],x;pushdown(x)) {
            if(ord-t[ls].siz>0) {
                if(!(ord-=t[ls].siz+1)) {splay(id,x); return x;}
                x=rs;
            } else x=ls;
        }
        abort(); return -1;
    }
    void addl(int id,int r,int v) {
        if(r<1) return;
        int root=rt[id];
        if(t[root].siz<=r) {add(root,v); return;}
        int x=findByOrder(id,r+1); splay(id,x); pushdown(x);
        if(t[x].son[0]) add(t[x].son[0],v),pushdown(t[x].son[0]),splay(id,t[x].son[0]);
    }
    void addr(int id,int l,int v) {
        int root=rt[id];
        if(l>t[root].siz) return;
        if(l<=1) {add(root,v); return;}
        int x=findByOrder(id,l-1); splay(id,x); pushdown(x);
        if(t[x].son[1]) add(t[x].son[1],v),pushdown(t[x].son[1]),splay(id,t[x].son[1]);
    }
    ll queryl(int id,int r) {
        if(r<1) return 0;
        int root=rt[id];
        if(t[root].siz<=r) {return t[root].sum;}
        int x=findByOrder(id,r+1); splay(id,x); pushdown(x);
        return t[t[x].son[0]].sum;
    }
    void mergex(int id,int x) {
        pushdown(x);
        if(t[x].son[0]) mergex(id,t[x].son[0]);
        insert(id,t[x].val);
        if(t[x].son[1]) mergex(id,t[x].son[1]);
        drop(x);
    }
    void merge(int i1,int i2) {
        if(!rt[i1]) {rt[i1]=rt[i2]; rt[i2]=0; return;}
        if(!rt[i2]) return;
        if(t[rt[i1]].siz>t[rt[i2]].siz) mergex(i1,rt[i2]),rt[i2]=0;
        else mergex(i2,rt[i1]),rt[i1]=rt[i2],rt[i2]=0;
    }
    void print(int x) {
        pushdown(x);
        if(t[x].son[0]) print(t[x].son[0]);
        cout<<t[x].val<<" ";
        if(t[x].son[1]) print(t[x].son[1]);
    }
}t;

int n,k;
vector<pair<int,int>> g[MAXN];

void dfs(int u,int fa,int wf) {
    for(auto [v,w]:g[u]) if(v!=fa) dfs(v,u,w),t.merge(u,v);
    t.insert(u,0); int mid=k/2;
    if(k&1) t.addl(u,mid,wf),t.addr(u,mid+2,-wf);
    else t.addl(u,mid,wf),t.addr(u,mid+1,-wf);
}

void solve() {
    cin>>n>>k;
    for(int i=1;i<n;++i) {
        int u,v,w; cin>>u>>v>>w;
        g[u].emplace_back(v,w); g[v].emplace_back(u,w);
    }
    dfs(1,0,0);
    cout<<t.queryl(1,k)*2<<"\n";
    t.clear(n);
    for(int i=1;i<=n;++i) g[i].clear();
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int T=1; cin>>T;
    while(T--) solve();

    return 0;
}