#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long inf = 1e9;
long long add(long long x, long long y) { return (1ll * x + 1ll * y) % mod; }
long long del(long long x, long long y) {
  return ((1ll * x - 1ll * y) % mod + mod) % mod;
}
long long mul(long long x, long long y) { return (1ll * x * 1ll * y) % mod; }
const long long N = 5e5 + 5;
long long n, k, q, dp[N][2];
vector<pair<long long, long long> > graph[N];
long long sum = 0;
void dfs(long long u, long long p) {
  for (long long i = 0; i < graph[u].size(); i++) {
    long long v = graph[u][i].first;
    if (v == p) continue;
    dfs(v, u);
  }
  long long hihi = 0, amount = 0;
  vector<long long> vec;
  for (long long i = 0; i < graph[u].size(); i++) {
    long long v = graph[u][i].first, w = graph[u][i].second;
    if (v == p) continue;
    amount += dp[v][1];
    hihi++;
    vec.push_back(-dp[v][1] + dp[v][0] + w);
  }
  if (vec.size() == 0) return;
  sort(vec.begin(), vec.end());
  if (hihi < k) {
    for (long long i = vec.size() - 1; i >= 0; i--) {
      if (vec[i] >= 0) amount += vec[i];
    }
    dp[u][0] = amount;
  } else {
    long long lmao1 = 0, amount1 = amount;
    for (long long i = vec.size() - 1; i >= 0; i--) {
      if (lmao1 == k) break;
      amount += vec[i];
      lmao1++;
    }
    dp[u][1] = amount;
    amount = amount1;
    long long lmao = 0;
    for (long long i = vec.size() - 1; i >= 0; i--) {
      if (lmao == k - 1) break;
      if (vec[i] > 0) amount += vec[i], lmao++;
    }
    dp[u][0] = amount;
  }
  dp[u][1] = max(dp[u][1], dp[u][0]);
}
signed main() {
  cin.tie(0), ios_base::sync_with_stdio(0);
  cin >> q;
  while (q--) {
    sum = 0;
    cin >> n >> k;
    for (long long i = 1; i <= n - 1; i++) {
      long long u, v, w;
      cin >> u >> v >> w;
      graph[u].push_back({v, w});
      graph[v].push_back({u, w});
    }
    dfs(1, 1);
    cout << max(dp[1][0], dp[1][1]) << "\n";
    for (long long i = 1; i <= n; i++) {
      graph[i].clear();
      dp[i][0] = dp[i][1] = 0;
    }
  }
}
