/*

给定一棵树，每个结点最多选和其相连的k条边，问使边权和最大的策略 

dp[u][0|1]用来表示u没连父边|连了父边 时u子树下的最优解

如果u不和任意一个儿子连边，那么u下的收益是tot=sum{dp[v][0]}

现在我们在其中选择一个儿子v连到u，那么 tot的增量就是 dv=dp[v][1]-dp[v][0] + w;

求dp[u][0]时，我们最多可以选择k个儿子相连，那么就把 所有dv进行排序，然后找前面k个大于0的即可

dp[u][1]同理，但是只要选择k-1个儿子即可

*/

#include<bits/stdc++.h>

#include<vector>

using namespace std;

#define N 500005

#define ll long long 

vector<pair<ll,ll> >G[N];

int n,k;

ll dp[N][];

int cmp(ll a,ll b){

    return a>b;

}

void dfs(int u,int pre){

    ll tot=;

    vector<ll>d;d.clear();

    for(auto p:G[u]){

        int v=p.first;

        if(v==pre)continue;

        dfs(v,u);

        d.push_back(dp[v][]-dp[v][]+p.second);

        tot+=dp[v][];

    }

    sort(d.begin(),d.end(),cmp);

    //求出dp[u][0]

    dp[u][]=tot;

    for(int i=;i<min(k,(int)d.size());i++)

        if(d[i]>)dp[u][]+=d[i];

    //求出dp[u][1]

    dp[u][]=tot;

    for(int i=;i<min(k-,(int)d.size());i++)

        if(d[i]>)dp[u][]+=d[i];

}

void init(){

    for(int i=;i<=n;i++)G[i].clear();

    for(int i=;i<=n;i++)dp[i][]=dp[i][]=;

}

int main(){

    int q;cin>>q;

    while(q--){

        init();

        cin>>n>>k;

        for(int i=;i<n;i++){

            int u,v,w;scanf("%d%d%d",&u,&v,&w);

            G[u].push_back(make_pair(v,w));

            G[v].push_back(make_pair(u,w));

        }

        /*for(int i=1;i<=n;i++){

            for(auto v:G[i])

                cout<<v.first<<" ";

            puts("");

        }*/

        dfs(,);

        cout<<dp[][]<<'\n';

    }

}