/*
[templates]: 
duipai
spjdp
compre
addhis
floor_sum
treedfs
matrix
network_flow
polynomial
lca
bitset
valuesgt
fenwick
erbitree
*/
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
#include<bits/stdc++.h>
using namespace std;
#define int long long
//use ll instead of int.
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e18;
//#define cerr if(false)cerr
//#define freopen if(false)freopen
mt19937 rng(time(0)); 
int rnd(int l, int r) {return rng() % (r-l+1) + l; }
#define watch(x) cerr  << (#x) << ' '<<'i'<<'s'<<' ' << x << endl
void pofe(int number, int bitnum) {
    string s; f(i, 0, bitnum) {s += char(number & 1) + '0'; number >>= 1; } 
    reverse(s.begin(), s.end()); cerr << s << endl; 
    return;
}
template <typename TYP> void cmax(TYP &x, TYP y) {if(x < y) x = y;}
template <typename TYP> void cmin(TYP &x, TYP y) {if(x > y) x = y;}
//调不出来给我对拍！
//use std::array.
vector<pii> t[200020]; int n, k; 
struct HEAP {
    priority_queue<int, vector<int>, greater<int>> q; 
    int tag; 
    void qing() {
        while(!q.empty()) q.pop(); 
        tag = 0; 
    }
    void jin(int shu) {
        q.push(shu - tag); 
    }
    int ding() {
        return q.top() + tag; 
    }
    void chu() {
        q.pop(); 
    }
    void jia(int shu) {
        tag += shu; 
    }
    void bing(HEAP op) {
        if(q.size() < op.q.size()) {
            swap(q, op.q);
            swap(tag, op.tag);  
        }
        while(!op.q.empty()) {
            q.push(op.ding() - tag); 
            op.chu(); 
        }
    }
}s[200020], p[200020], x[200020]; 
void dfs(int now, int fa) {
    for(pii iw : t[now]) {
        int i = iw.first, w = iw.second; 
        if(i == fa) continue;
        dfs(i, now); 
        s[i].jia(w); x[i].jia(-w); 
        s[now].bing(s[i]); 
        p[now].bing(p[i]); 
        x[now].bing(x[i]); 
    }
    s[now].jin(0); 
    while((int)s[now].q.size() > k / 2) {p[now].jin(s[now].ding()); s[now].chu(); }
    while((int)p[now].q.size() > k % 2) {x[now].jin(p[now].ding()); p[now].chu(); }
    // cerr << "now = " << now << ", " << s[now].q.size() << " " << p[now].q.size() << " " << x[now].q.size() << endl; 
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen();
    //freopen();
    //time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    int T; cin >> T;
    while(T--) {
        cin >> n >> k; 
        f(i, 1, n - 1) {
            int u, v, w; cin >> u >> v >> w; 
            t[u].push_back({v, w}); t[v].push_back({u, w}); 
        }
        f(i, 1, n) {
            s[i].qing(); 
            p[i].qing(); 
            x[i].qing(); 
        }
        dfs(1, 0); 
        s[1].bing(p[1]); s[1].bing(x[1]); 
        int cur = 0; vector<int> res; 
        while(!s[1].q.empty()) {
            res.push_back(s[1].ding()); 
            s[1].chu(); 
        }
        reverse(res.begin(), res.end()); 
        f(i, 0, k - 1) {
            cur += res[i];
        }
        cout << 2 * cur << endl; 
    }
    //time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
}