#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
const ll mod = 998244353;
priority_queue<ll,vector<ll>,greater<ll>>up[200005], mid[200005], dw[200005];
ll lazyup[200005],lazymid[200005],lazydw[200005];
int n,k;
vector<P>edge[200005];
void look(priority_queue<ll,vector<ll>,greater<ll>>&que,ll x){
vector<ll>vec;
while(que.size()){ vec.pb(que.top()); que.pop(); }
reverse(vec.begin(),vec.end());
for(auto v:vec) cout << v+x << " ";
cout << endl;
for(auto v:vec) que.push(v);
}
void dfs(int v,int u){
P mx = mp(0,0);
rep(i,edge[v].size()){
if(edge[v][i].fi == u) continue;
dfs(edge[v][i].fi,v);
if(mx < mp((int)(up[edge[v][i].fi].size() + mid[edge[v][i].fi].size() + dw[edge[v][i].fi].size()), edge[v][i].fi)){
mx = mp((int)(up[edge[v][i].fi].size() + mid[edge[v][i].fi].size() + dw[edge[v][i].fi].size()), edge[v][i].fi);
}
}
if(mx.sc == 0){
up[v].push(0);
return;
}
else{
swap(up[v],up[mx.sc]);
swap(mid[v],mid[mx.sc]);
swap(dw[v],dw[mx.sc]);
lazyup[v] = lazyup[mx.sc];
lazymid[v] = lazymid[mx.sc];
lazydw[v] = lazydw[mx.sc];
}
rep(i,edge[v].size()){
if(edge[v][i].fi == mx.sc){
lazyup[v] += 2 * edge[v][i].sc;
lazydw[v] -= 2 * edge[v][i].sc;
break;
}
}
rep(i,edge[v].size()){
if(edge[v][i].fi == u) continue;
if(edge[v][i].fi == mx.sc) continue;
while(up[edge[v][i].fi].size()){
ll x = up[edge[v][i].fi].top() + lazyup[edge[v][i].fi] + 2 * edge[v][i].sc;
up[v].push(x - lazyup[v]);
up[edge[v][i].fi].pop();
}
while(mid[edge[v][i].fi].size()){
ll x = mid[edge[v][i].fi].top() + lazymid[edge[v][i].fi];
up[v].push(x - lazyup[v]);
mid[edge[v][i].fi].pop();
}
while(dw[edge[v][i].fi].size()){
ll x = dw[edge[v][i].fi].top() + lazydw[edge[v][i].fi] - 2 * edge[v][i].sc;
up[v].push(x - lazyup[v]);
dw[edge[v][i].fi].pop();
}
}
up[v].push(-lazyup[v]);
while(up[v].size() > k/2){
ll x = up[v].top() + lazyup[v]; up[v].pop();
mid[v].push(x - lazymid[v]);
}
while(mid[v].size() > k%2){
ll x = mid[v].top() + lazymid[v]; mid[v].pop();
dw[v].push(x - lazydw[v]);
}
//cout << v << "_______" << endl;
//look(up[v],lazyup[v]);
//look(mid[v],lazymid[v]);
//look(dw[v],lazydw[v]);
}
void solve(){
scanf("%d%d",&n,&k);
repn(i,n){
while(up[i].size()) up[i].pop();
while(mid[i].size()) mid[i].pop();
while(dw[i].size()) dw[i].pop();
edge[i].clear();
lazyup[i] = lazymid[i] = lazydw[i] = 0;
}
rep(i,n-1){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
edge[a].pb(mp(b,c));
edge[b].pb(mp(a,c));
}
if(k == 1){
puts("0");
return ;
}
dfs(1,-1);
ll ans = 0;
int use = 0;
vector<ll>vec;
while(up[1].size()){ vec.pb(up[1].top() + lazyup[1]); up[1].pop(); use++; }
while(mid[1].size()){ vec.pb(mid[1].top() + lazymid[1]); mid[1].pop(); use++; }
while(dw[1].size()){ vec.pb(dw[1].top() + lazydw[1]); dw[1].pop(); use++; }
sort(vec.begin(),vec.end(),greater<ll>());
rep(i,k) ans += vec[i];
//assert(use == k);
printf("%lld\n",ans);
}
int main(){
int t; scanf("%d",&t);
while(t--) solve();
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHBhaXI8aW50LGludD4gUDsKdHlwZWRlZiBwYWlyPGludCxQPiBQMTsKdHlwZWRlZiBwYWlyPFAsUD4gUDI7CiNkZWZpbmUgcHUgcHVzaAojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIGVwcyAxZS03CiNkZWZpbmUgSU5GIDEwMDAwMDAwMDAKCiNkZWZpbmUgZmkgZmlyc3QKI2RlZmluZSBzYyBzZWNvbmQKI2RlZmluZSByZXAoaSx4KSBmb3IoaW50IGk9MDtpPHg7aSsrKQojZGVmaW5lIHJlcG4oaSx4KSBmb3IoaW50IGk9MTtpPD14O2krKykKI2RlZmluZSBTT1JUKHgpIHNvcnQoeC5iZWdpbigpLHguZW5kKCkpCiNkZWZpbmUgRVJBU0UoeCkgeC5lcmFzZSh1bmlxdWUoeC5iZWdpbigpLHguZW5kKCkpLHguZW5kKCkpCiNkZWZpbmUgUE9TTCh4LHYpIChsb3dlcl9ib3VuZCh4LmJlZ2luKCkseC5lbmQoKSx2KS14LmJlZ2luKCkpCiNkZWZpbmUgUE9TVSh4LHYpICh1cHBlcl9ib3VuZCh4LmJlZ2luKCkseC5lbmQoKSx2KS14LmJlZ2luKCkpCgpjb25zdCBsbCBtb2QgPSA5OTgyNDQzNTM7Cgpwcmlvcml0eV9xdWV1ZTxsbCx2ZWN0b3I8bGw+LGdyZWF0ZXI8bGw+PnVwWzIwMDAwNV0sIG1pZFsyMDAwMDVdLCBkd1syMDAwMDVdOwpsbCBsYXp5dXBbMjAwMDA1XSxsYXp5bWlkWzIwMDAwNV0sbGF6eWR3WzIwMDAwNV07CgppbnQgbixrOwp2ZWN0b3I8UD5lZGdlWzIwMDAwNV07CnZvaWQgbG9vayhwcmlvcml0eV9xdWV1ZTxsbCx2ZWN0b3I8bGw+LGdyZWF0ZXI8bGw+PiZxdWUsbGwgeCl7CiAgICB2ZWN0b3I8bGw+dmVjOwogICAgd2hpbGUocXVlLnNpemUoKSl7IHZlYy5wYihxdWUudG9wKCkpOyBxdWUucG9wKCk7IH0KICAgIHJldmVyc2UodmVjLmJlZ2luKCksdmVjLmVuZCgpKTsKICAgIGZvcihhdXRvIHY6dmVjKSBjb3V0IDw8IHYreCA8PCAiICI7CiAgICBjb3V0IDw8IGVuZGw7CiAgICBmb3IoYXV0byB2OnZlYykgcXVlLnB1c2godik7Cn0Kdm9pZCBkZnMoaW50IHYsaW50IHUpewoJUCBteCA9IG1wKDAsMCk7CglyZXAoaSxlZGdlW3ZdLnNpemUoKSl7CgkJaWYoZWRnZVt2XVtpXS5maSA9PSB1KSBjb250aW51ZTsKCQlkZnMoZWRnZVt2XVtpXS5maSx2KTsKCQlpZihteCA8IG1wKChpbnQpKHVwW2VkZ2Vbdl1baV0uZmldLnNpemUoKSArIG1pZFtlZGdlW3ZdW2ldLmZpXS5zaXplKCkgKyBkd1tlZGdlW3ZdW2ldLmZpXS5zaXplKCkpLCBlZGdlW3ZdW2ldLmZpKSl7CgkJCW14ID0gbXAoKGludCkodXBbZWRnZVt2XVtpXS5maV0uc2l6ZSgpICsgbWlkW2VkZ2Vbdl1baV0uZmldLnNpemUoKSArIGR3W2VkZ2Vbdl1baV0uZmldLnNpemUoKSksIGVkZ2Vbdl1baV0uZmkpOwoJCX0KCX0KCWlmKG14LnNjID09IDApewoJCXVwW3ZdLnB1c2goMCk7CgkJcmV0dXJuOwoJfQoJZWxzZXsKCQlzd2FwKHVwW3ZdLHVwW214LnNjXSk7CgkJc3dhcChtaWRbdl0sbWlkW214LnNjXSk7CgkJc3dhcChkd1t2XSxkd1tteC5zY10pOwoJCWxhenl1cFt2XSA9IGxhenl1cFtteC5zY107CgkJbGF6eW1pZFt2XSA9IGxhenltaWRbbXguc2NdOwoJCWxhenlkd1t2XSA9IGxhenlkd1tteC5zY107Cgl9CglyZXAoaSxlZGdlW3ZdLnNpemUoKSl7CgkgICAgaWYoZWRnZVt2XVtpXS5maSA9PSBteC5zYyl7CgkgICAgICAgIGxhenl1cFt2XSArPSAyICogZWRnZVt2XVtpXS5zYzsKCSAgICAgICAgbGF6eWR3W3ZdIC09IDIgKiBlZGdlW3ZdW2ldLnNjOwoJICAgICAgICBicmVhazsKCSAgICB9Cgl9CglyZXAoaSxlZGdlW3ZdLnNpemUoKSl7CgkJaWYoZWRnZVt2XVtpXS5maSA9PSB1KSBjb250aW51ZTsKCQlpZihlZGdlW3ZdW2ldLmZpID09IG14LnNjKSBjb250aW51ZTsKCQl3aGlsZSh1cFtlZGdlW3ZdW2ldLmZpXS5zaXplKCkpewoJCQlsbCB4ID0gdXBbZWRnZVt2XVtpXS5maV0udG9wKCkgKyBsYXp5dXBbZWRnZVt2XVtpXS5maV0gKyAyICogZWRnZVt2XVtpXS5zYzsKCQkJdXBbdl0ucHVzaCh4IC0gbGF6eXVwW3ZdKTsKCQkJdXBbZWRnZVt2XVtpXS5maV0ucG9wKCk7CgkJfQoJCXdoaWxlKG1pZFtlZGdlW3ZdW2ldLmZpXS5zaXplKCkpewoJCQlsbCB4ID0gbWlkW2VkZ2Vbdl1baV0uZmldLnRvcCgpICsgbGF6eW1pZFtlZGdlW3ZdW2ldLmZpXTsKCQkJdXBbdl0ucHVzaCh4IC0gbGF6eXVwW3ZdKTsKCQkJbWlkW2VkZ2Vbdl1baV0uZmldLnBvcCgpOwoJCX0KCQl3aGlsZShkd1tlZGdlW3ZdW2ldLmZpXS5zaXplKCkpewoJCQlsbCB4ID0gZHdbZWRnZVt2XVtpXS5maV0udG9wKCkgKyBsYXp5ZHdbZWRnZVt2XVtpXS5maV0gLSAyICogZWRnZVt2XVtpXS5zYzsKCQkJdXBbdl0ucHVzaCh4IC0gbGF6eXVwW3ZdKTsKCQkJZHdbZWRnZVt2XVtpXS5maV0ucG9wKCk7CgkJfQoJfQoJdXBbdl0ucHVzaCgtbGF6eXVwW3ZdKTsKCXdoaWxlKHVwW3ZdLnNpemUoKSA+IGsvMil7CgkJbGwgeCA9IHVwW3ZdLnRvcCgpICsgbGF6eXVwW3ZdOyB1cFt2XS5wb3AoKTsKCQltaWRbdl0ucHVzaCh4IC0gbGF6eW1pZFt2XSk7Cgl9Cgl3aGlsZShtaWRbdl0uc2l6ZSgpID4gayUyKXsKCQlsbCB4ID0gbWlkW3ZdLnRvcCgpICsgbGF6eW1pZFt2XTsgbWlkW3ZdLnBvcCgpOwoJCWR3W3ZdLnB1c2goeCAtIGxhenlkd1t2XSk7Cgl9CgkvL2NvdXQgPDwgdiA8PCAiX19fX19fXyIgPDwgZW5kbDsKCS8vbG9vayh1cFt2XSxsYXp5dXBbdl0pOwoJLy9sb29rKG1pZFt2XSxsYXp5bWlkW3ZdKTsKCS8vbG9vayhkd1t2XSxsYXp5ZHdbdl0pOwp9CnZvaWQgc29sdmUoKXsKICAgIHNjYW5mKCIlZCVkIiwmbiwmayk7CiAgICByZXBuKGksbil7CiAgICAgICAgd2hpbGUodXBbaV0uc2l6ZSgpKSB1cFtpXS5wb3AoKTsKICAgICAgICB3aGlsZShtaWRbaV0uc2l6ZSgpKSBtaWRbaV0ucG9wKCk7CiAgICAgICAgd2hpbGUoZHdbaV0uc2l6ZSgpKSBkd1tpXS5wb3AoKTsKICAgICAgICBlZGdlW2ldLmNsZWFyKCk7CiAgICAgICAgbGF6eXVwW2ldID0gbGF6eW1pZFtpXSA9IGxhenlkd1tpXSA9IDA7CiAgICB9CiAgICByZXAoaSxuLTEpewogICAgCWludCBhLGIsYzsKICAgIAlzY2FuZigiJWQlZCVkIiwmYSwmYiwmYyk7CiAgICAJZWRnZVthXS5wYihtcChiLGMpKTsKICAgIAllZGdlW2JdLnBiKG1wKGEsYykpOwogICAgfQogICAgaWYoayA9PSAxKXsKICAgIAlwdXRzKCIwIik7CiAgICAJcmV0dXJuIDsKICAgIH0KICAgIGRmcygxLC0xKTsKICAgIGxsIGFucyA9IDA7CiAgICBpbnQgdXNlID0gMDsKICAgIHZlY3RvcjxsbD52ZWM7CiAgICB3aGlsZSh1cFsxXS5zaXplKCkpeyB2ZWMucGIodXBbMV0udG9wKCkgKyBsYXp5dXBbMV0pOyB1cFsxXS5wb3AoKTsgdXNlKys7IH0KICAgIHdoaWxlKG1pZFsxXS5zaXplKCkpeyB2ZWMucGIobWlkWzFdLnRvcCgpICsgbGF6eW1pZFsxXSk7IG1pZFsxXS5wb3AoKTsgdXNlKys7IH0KICAgIHdoaWxlKGR3WzFdLnNpemUoKSl7IHZlYy5wYihkd1sxXS50b3AoKSArIGxhenlkd1sxXSk7IGR3WzFdLnBvcCgpOyB1c2UrKzsgfQogICAgc29ydCh2ZWMuYmVnaW4oKSx2ZWMuZW5kKCksZ3JlYXRlcjxsbD4oKSk7CiAgICByZXAoaSxrKSBhbnMgKz0gdmVjW2ldOwoJLy9hc3NlcnQodXNlID09IGspOwoJcHJpbnRmKCIlbGxkXG4iLGFucyk7Cn0KaW50IG1haW4oKXsKCWludCB0OyBzY2FuZigiJWQiLCZ0KTsKCXdoaWxlKHQtLSkgc29sdmUoKTsKfQ==