#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 10, INF = 0x3f3f3f3f;
vector<pair<int, int>> g[MAXN];
long long memo[MAXN][2];
int k, n;
long long dp(int v, int fa, int f) {
  if (g[v].size() == 1 && g[v][0].first == fa) return 0;
  if (memo[v][f] != -1) return memo[v][f];
  vector<long long> weights;
  auto &ans = memo[v][1] = 0;
  for (auto e : g[v]) {
    int u = e.first, w = e.second;
    if (u == fa) continue;
    if (dp(u, v, 1) + w - dp(u, v, 0) > 0)
      weights.emplace_back(dp(u, v, 1) + w - dp(u, v, 0));
    ans += dp(u, v, 0);
  }
  sort(weights.begin(), weights.end(), greater<int>());
  int take = k - 1;
  take = min(take, (int)weights.size());
  for (int i = 0; i < take; i++) ans += weights[i];
  memo[v][0] = memo[v][1];
  if (k - 1 < weights.size()) memo[v][0] += weights[k - 1];
  return memo[v][f];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    cin >> n >> k;
    for (int i = 0; i < n; i++) g[i].clear(), memo[i][0] = memo[i][1] = -1;
    for (int i = 0; i < n - 1; i++) {
      int u, v, w;
      cin >> u >> v >> w;
      u--;
      v--;
      g[v].emplace_back(u, w);
      g[u].emplace_back(v, w);
    }
    cout << dp(0, -1, 0) << endl;
  }
  return 0;
}
