#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=201000;
int n,u,v,w,rt,T,_,mt[N],cnt[N],k,pv[N],mark[N];
ll ans;
vector<PII> e[N];
vector<array<ll,3>> dis;
void dfs(int u,int f,int br,ll d) {
dis.pb({d,br,u});
for (auto p:e[u]) {
int v=p.fi;
if (v==f) continue;
dfs(v,u,br==rt?v:br,d+p.se);
}
}
void solve(int x) {
rt=x;
dis.clear();
dfs(rt,0,rt,0);
sort(all(dis)); reverse(all(dis));
T++;
ll tmp=0;
int pt=0;
for (auto x:dis) {
if (mt[x[1]]!=T) mt[x[1]]=T,cnt[x[1]]=0;
if (pt<k&&cnt[x[1]]<k/2) { pt++; cnt[x[1]]++; tmp+=x[0]; mark[x[2]]=T; }
}
if (pt==k&&tmp>ans) {
ans=tmp; rt=x;
rep(i,1,n+1) pv[i]=(mark[i]==T);
}
}
int q[N],f[N],vis[N],sz[N],ms[N];
int find(int u) {
int t=1;q[0]=u;f[u]=-1;
rep(i,0,t) {
u=q[i];
rep(j,0,e[u].size()) {
int v=e[u][j].fi;
if (!vis[v]&&v!=f[u]) f[q[t++]=v]=u;
}
ms[q[i]]=0;
sz[q[i]]=1;
}
for (int i=t-1;i>=0;i--) {
ms[q[i]]=max(ms[q[i]],t-sz[q[i]]);
if (ms[q[i]]*2<=t) return q[i];
sz[f[q[i]]]+=sz[q[i]];
ms[f[q[i]]]=max(ms[f[q[i]]],sz[q[i]]);
}
return 0;
}
void gao(int u) {
u=find(u);
solve(u);
T++;
int maj=-1;
rep(i,0,k) {
auto x=dis[i];
// printf("dd %lld %lld %lld\n",x[0],x[1],x[2]);
if (mt[x[1]]!=T) mt[x[1]]=T,cnt[x[1]]=0;
cnt[x[1]]++;
if (cnt[x[1]]>k/2) maj=x[1];
}
vis[u]=1;
//fprintf(stderr,"%d %d\n",u,maj);
if (maj!=-1&&!vis[maj]) gao(maj);
}
pair<ll,int> dfs(int u,int f) {
int fv=pv[u];
ll mdis=0;
for (auto p:e[u]) {
int v=p.fi;
if (v==f) continue;
auto z=dfs(v,u);
if (z.se<k/2) z.fi+=p.se;
fv+=z.se;
mdis=max(mdis,z.fi);
}
if (pv[u]) mdis=-(1ll<<60);
return mp(mdis,fv);
}
void solve() {
scanf("%d%d",&n,&k);
rep(i,1,n+1) e[i].clear(),vis[i]=0;
ans=0;
for (int i=1;i<n;i++) {
scanf("%d%d%d",&u,&v,&w);
e[u].pb(mp(v,w));
e[v].pb(mp(u,w));
}
if (k%2==1) {
--k;
gao(1);
ans+=dfs(rt,0).fi;
} else gao(1);
printf("%lld\n",2*ans);
}
int main() {
for (scanf("%d",&_);_;_--) solve();
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgcmVwKGksYSxuKSBmb3IgKGludCBpPWE7aTxuO2krKykKI2RlZmluZSBwZXIoaSxhLG4pIGZvciAoaW50IGk9bi0xO2k+PWE7aS0tKQojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIGFsbCh4KSAoeCkuYmVnaW4oKSwoeCkuZW5kKCkKI2RlZmluZSBmaSBmaXJzdAojZGVmaW5lIHNlIHNlY29uZAojZGVmaW5lIFNaKHgpICgoaW50KSh4KS5zaXplKCkpCnR5cGVkZWYgdmVjdG9yPGludD4gVkk7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHBhaXI8aW50LGludD4gUElJOwp0eXBlZGVmIGRvdWJsZSBkYjsKbXQxOTkzNyBtcmFuZChyYW5kb21fZGV2aWNle30oKSk7IApjb25zdCBsbCBtb2Q9MTAwMDAwMDAwNzsKaW50IHJuZChpbnQgeCkgeyByZXR1cm4gbXJhbmQoKSAlIHg7fQpsbCBwb3dtb2QobGwgYSxsbCBiKSB7bGwgcmVzPTE7YSU9bW9kOyBhc3NlcnQoYj49MCk7IGZvcig7YjtiPj49MSl7aWYoYiYxKXJlcz1yZXMqYSVtb2Q7YT1hKmElbW9kO31yZXR1cm4gcmVzO30KbGwgZ2NkKGxsIGEsbGwgYikgeyByZXR1cm4gYj9nY2QoYixhJWIpOmE7fQovLyBoZWFkCgpjb25zdCBpbnQgTj0yMDEwMDA7CmludCBuLHUsdix3LHJ0LFQsXyxtdFtOXSxjbnRbTl0sayxwdltOXSxtYXJrW05dOwpsbCBhbnM7CnZlY3RvcjxQSUk+IGVbTl07CnZlY3RvcjxhcnJheTxsbCwzPj4gZGlzOwoKdm9pZCBkZnMoaW50IHUsaW50IGYsaW50IGJyLGxsIGQpIHsKCWRpcy5wYih7ZCxicix1fSk7Cglmb3IgKGF1dG8gcDplW3VdKSB7CgkJaW50IHY9cC5maTsKCQlpZiAodj09ZikgY29udGludWU7CgkJZGZzKHYsdSxicj09cnQ/djpicixkK3Auc2UpOwoJfQp9Cgp2b2lkIHNvbHZlKGludCB4KSB7CglydD14OwoJZGlzLmNsZWFyKCk7CglkZnMocnQsMCxydCwwKTsKCXNvcnQoYWxsKGRpcykpOyByZXZlcnNlKGFsbChkaXMpKTsKCVQrKzsKCWxsIHRtcD0wOwoJaW50IHB0PTA7Cglmb3IgKGF1dG8geDpkaXMpIHsKCQlpZiAobXRbeFsxXV0hPVQpIG10W3hbMV1dPVQsY250W3hbMV1dPTA7CgkJaWYgKHB0PGsmJmNudFt4WzFdXTxrLzIpIHsgcHQrKzsgY250W3hbMV1dKys7IHRtcCs9eFswXTsgbWFya1t4WzJdXT1UOyB9Cgl9CglpZiAocHQ9PWsmJnRtcD5hbnMpIHsKCQlhbnM9dG1wOyBydD14OwoJCXJlcChpLDEsbisxKSBwdltpXT0obWFya1tpXT09VCk7Cgl9Cn0KCmludCBxW05dLGZbTl0sdmlzW05dLHN6W05dLG1zW05dOwppbnQgZmluZChpbnQgdSkgewoJaW50IHQ9MTtxWzBdPXU7Zlt1XT0tMTsKCXJlcChpLDAsdCkgewoJCXU9cVtpXTsKCQlyZXAoaiwwLGVbdV0uc2l6ZSgpKSB7CgkJCWludCB2PWVbdV1bal0uZmk7CgkJCWlmICghdmlzW3ZdJiZ2IT1mW3VdKSBmW3FbdCsrXT12XT11OwoJCX0KCQltc1txW2ldXT0wOwoJCXN6W3FbaV1dPTE7Cgl9Cglmb3IgKGludCBpPXQtMTtpPj0wO2ktLSkgewoJCW1zW3FbaV1dPW1heChtc1txW2ldXSx0LXN6W3FbaV1dKTsKCQlpZiAobXNbcVtpXV0qMjw9dCkgcmV0dXJuIHFbaV07CgkJc3pbZltxW2ldXV0rPXN6W3FbaV1dOwoJCW1zW2ZbcVtpXV1dPW1heChtc1tmW3FbaV1dXSxzeltxW2ldXSk7Cgl9CglyZXR1cm4gMDsKfQoKdm9pZCBnYW8oaW50IHUpIHsKCXU9ZmluZCh1KTsKCXNvbHZlKHUpOwoJVCsrOwoJaW50IG1haj0tMTsKCXJlcChpLDAsaykgewoJCWF1dG8geD1kaXNbaV07CgkvLwlwcmludGYoImRkICVsbGQgJWxsZCAlbGxkXG4iLHhbMF0seFsxXSx4WzJdKTsKCQlpZiAobXRbeFsxXV0hPVQpIG10W3hbMV1dPVQsY250W3hbMV1dPTA7CgkJY250W3hbMV1dKys7CgkJaWYgKGNudFt4WzFdXT5rLzIpIG1haj14WzFdOwoJfQoJdmlzW3VdPTE7CgkvL2ZwcmludGYoc3RkZXJyLCIlZCAlZFxuIix1LG1haik7CglpZiAobWFqIT0tMSYmIXZpc1ttYWpdKSBnYW8obWFqKTsKfQoKcGFpcjxsbCxpbnQ+IGRmcyhpbnQgdSxpbnQgZikgewoJaW50IGZ2PXB2W3VdOwoJbGwgbWRpcz0wOwoJZm9yIChhdXRvIHA6ZVt1XSkgewoJCWludCB2PXAuZmk7CgkJaWYgKHY9PWYpIGNvbnRpbnVlOwoJCWF1dG8gej1kZnModix1KTsKCQlpZiAoei5zZTxrLzIpIHouZmkrPXAuc2U7CgkJZnYrPXouc2U7CgkJbWRpcz1tYXgobWRpcyx6LmZpKTsKCX0KCWlmIChwdlt1XSkgbWRpcz0tKDFsbDw8NjApOwoJcmV0dXJuIG1wKG1kaXMsZnYpOwp9Cgp2b2lkIHNvbHZlKCkgewoJc2NhbmYoIiVkJWQiLCZuLCZrKTsKCXJlcChpLDEsbisxKSBlW2ldLmNsZWFyKCksdmlzW2ldPTA7CglhbnM9MDsKCWZvciAoaW50IGk9MTtpPG47aSsrKSB7CgkJc2NhbmYoIiVkJWQlZCIsJnUsJnYsJncpOwoJCWVbdV0ucGIobXAodix3KSk7CgkJZVt2XS5wYihtcCh1LHcpKTsKCX0KCWlmIChrJTI9PTEpIHsKCQktLWs7CgkJZ2FvKDEpOwoJCWFucys9ZGZzKHJ0LDApLmZpOwoJfSBlbHNlIGdhbygxKTsKCXByaW50ZigiJWxsZFxuIiwyKmFucyk7CQp9CgppbnQgbWFpbigpIHsKCWZvciAoc2NhbmYoIiVkIiwmXyk7XztfLS0pIHNvbHZlKCk7Cn0K