#include <bits/stdc++.h>
using namespace std;
long long T, N, K, dp[500005][2];
vector<pair<long long, long long>> routes[500005];
bool seen[500005];
vector<long long> best[500005];
void solve(long long node) {
  bool ok = true;
  for (auto child : routes[node]) {
    if (!seen[child.second]) {
      seen[child.second] = true;
      ok = false;
      solve(child.second);
      dp[child.second][1] += child.first;
      dp[node][0] += dp[child.second][0];
      dp[node][1] += dp[child.second][0];
      best[node].push_back(dp[child.second][1] - dp[child.second][0]);
    }
  }
  if (ok) {
    return;
  }
  sort(best[node].rbegin(), best[node].rend());
  for (long long i = 0; i < min(K, (long long)best[node].size()); ++i) {
    dp[node][0] += max(0LL, best[node][i]);
  }
  for (long long i = 0; i < min(K - 1, (long long)best[node].size()); ++i) {
    dp[node][1] += max(0LL, best[node][i]);
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> T;
  for (long long t = 0; t < T; ++t) {
    cin >> N >> K;
    long long u, v, w;
    for (long long i = 0; i < N - 1; ++i) {
      cin >> u >> v >> w;
      routes[u].push_back({w, v});
      routes[v].push_back({w, u});
    }
    seen[1] = true;
    solve(1);
    cout << max(dp[1][0], dp[1][1]) << "\n";
    for (long long i = 0; i <= N; ++i) {
      routes[i].clear();
      best[i].clear();
    }
    fill(begin(seen), begin(seen) + N + 1, false);
    fill(dp[0], dp[N + 1], 0);
  }
}
