#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
const int maxn = 5e5 + 5;
int n, k;
vector<ii> g[maxn];
ll dp[maxn][2];
void solve(int u, int par) {
  for (ii e : g[u]) {
    int v = e.first;
    ll w = e.second;
    if (v - par) {
      solve(v, u);
    }
  }
  ll tot0 = 0;
  vector<ll> pot;
  for (ii e : g[u]) {
    int v = e.first;
    ll w = e.second;
    if (v - par) {
      tot0 += dp[v][0];
      pot.emplace_back(w + dp[v][1] - dp[v][0]);
    }
  }
  sort(pot.begin(), pot.end());
  reverse(pot.begin(), pot.end());
  dp[u][0] = dp[u][1] = tot0;
  for (int i = 0; i < k and i < pot.size() and pot[i] > 0; i++) {
    dp[u][0] += pot[i];
  }
  for (int i = 0; i < k - 1 and i < pot.size() and pot[i] > 0; i++) {
    dp[u][1] += pot[i];
  }
}
int main(int argc, char const *argv[]) {
  int tc;
  scanf("%d", &tc);
  while (tc--) {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
      g[i].clear();
    }
    for (int i = 1; i < n; i++) {
      int u, v, w;
      scanf("%d %d %d", &u, &v, &w);
      g[u].emplace_back(v, w);
      g[v].emplace_back(u, w);
    }
    solve(1, -1);
    printf("%lld\n", dp[1][0]);
  }
  return 0;
}
