#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e4 + ;

struct edge{

    int from,to,len,id;

    edge(int a = ,int b = ,int c = ,int d = ){

        from = a,to = b,len = c,id = d;

    }

    bool operator< (const edge& e) const{

        return len < e.len;

    }

};

int indegree[maxn];

bool visit[maxn];

edge store[maxn];

priority_queue<edge> pq;

void init(){

    memset(visit,false,sizeof(visit));

    memset(indegree,,sizeof(indegree));

    while(pq.size()) pq.pop();

}

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        int n,k;

        LL sum = ;

        init();

        scanf("%d%d",&n,&k);

        int from,to,len;

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

            scanf("%d%d%d",&from,&to,&len);

            store[i] = edge(from,to,len,i);

            sum += len;

            indegree[from] += ;

            indegree[to] += ;

        }

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

            edge& e = store[i];

            if(indegree[e.from] ==  || indegree[e.to] == ){

                pq.push(e);

                visit[e.id] = true;

            }

        }

        LL ans = ;

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

            edge e = pq.top();

            pq.pop();

            --indegree[e.from];

            --indegree[e.to];

            ans += e.len;

            for(int j = ;j < n - ;++j){

                if(visit[j]) continue;

                edge ee = store[j];

                if(indegree[ee.from] ==  || indegree[ee.to] == ){

                    pq.push(ee);

                    visit[ee.id] = true;

                }

            }

        }

        ans = sum - ans;

        ans *= ;

        printf("%lld\n",ans);

    }

    return ;

}