#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<pair<int, int> > vec[500005];
long long dp[500005][2];
bool cmp(pair<long long, long long> a, pair<long long, long long> b) {
  return a.first - a.second > b.first - b.second;
}
void dfs(int s, int par = 0) {
  vector<pair<long long, long long> > tmp;
  for (pair<int, int> p : vec[s]) {
    int v = p.first, c = p.second;
    if (v == par) continue;
    dfs(v, s);
    tmp.push_back({c + dp[v][1], dp[v][0]});
  }
  sort(tmp.begin(), tmp.end(), cmp);
  dp[s][0] = 0;
  for (int i = 0; i < min((int)tmp.size(), k); i++) {
    if (tmp[i].first > tmp[i].second)
      dp[s][0] += tmp[i].first;
    else
      dp[s][0] += tmp[i].second;
  }
  for (int i = k; i < tmp.size(); i++) dp[s][0] += tmp[i].second;
  dp[s][1] = 0;
  for (int i = 0; i < min((int)tmp.size(), k - 1); i++) {
    if (tmp[i].first > tmp[i].second)
      dp[s][1] += tmp[i].first;
    else
      dp[s][1] += tmp[i].second;
  }
  for (int i = k - 1; i < tmp.size(); i++) dp[s][1] += tmp[i].second;
}
int main() {
  int q;
  scanf("%d", &q);
  while (q--) {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) vec[i].clear();
    for (int i = 1; i < n; i++) {
      int u, v, c;
      scanf("%d %d %d", &u, &v, &c);
      vec[u].push_back({v, c});
      vec[v].push_back({u, c});
    }
    dfs(1);
    printf("%lld\n", dp[1][0]);
  }
  return 0;
}
