#include <bits/stdc++.h>
using namespace std;
const long long N = 500010;
long long n, k;
long long dp[N][2];
vector<pair<long long, long long>> g[N];
void dfs(long long v, long long p) {
  vector<pair<long long, long long>> s;
  for (auto [w, u] : g[v]) {
    if (u != p) {
      dfs(u, v);
      s.emplace_back(dp[u][1] + w, dp[u][0]);
    }
  }
  sort(s.begin(), s.end(),
       [&](const pair<long long, long long> &p1,
           const pair<long long, long long> &p2) {
         return p1.first - p1.second > p2.first - p2.second;
       });
  dp[v][0] = 0;
  dp[v][1] = 0;
  for (long long i = 0; i < (long long)s.size(); i++) {
    if (i < k && s[i].first > s[i].second) {
      dp[v][0] += s[i].first;
    } else {
      dp[v][0] += s[i].second;
    }
    if (i < k - 1 && s[i].first > s[i].second) {
      dp[v][1] += s[i].first;
    } else {
      dp[v][1] += s[i].second;
    }
  }
}
void solve() {
  cin >> n >> k;
  for (long long i = 0; i < n - 1; i++) {
    long long v, u, w;
    cin >> v >> u >> w;
    v--;
    u--;
    g[v].emplace_back(w, u);
    g[u].emplace_back(w, v);
  }
  dfs(0, -1);
  cout << dp[0][0] << '\n';
  for (long long i = 0; i < n; i++) {
    g[i].clear();
    g[i].shrink_to_fit();
  }
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long q;
  cin >> q;
  while (q--) {
    solve();
  }
  return 0;
}
