#include <bits/stdc++.h>
const int N = 5e5 + 5;
int n, k, T;
const long long INF = 1e18;
std::vector<std::pair<int, int> > g[N];
long long dp[N][2];
void dfs(int u, int fa) {
  dp[u][0] = dp[u][1] = 0;
  std::vector<long long> f;
  for (std::pair<int, int> c : g[u])
    if (c.first != fa) {
      int v = c.first;
      dfs(v, u);
      dp[u][0] += dp[v][0];
      f.push_back(dp[v][1] + c.second - dp[v][0]);
    }
  std::sort(f.begin(), f.end(), std::greater<long long>());
  dp[u][1] = dp[u][0];
  for (int i = 0; i < k && i < f.size(); i++) {
    dp[u][0] += std::max(0LL, f[i]);
  }
  for (int i = 0; i < k - 1 && i < f.size(); i++) {
    dp[u][1] += std::max(0LL, f[i]);
  }
}
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) g[i].clear();
    for (int i = 1, u, v, c; i < n; i++) {
      scanf("%d%d%d", &u, &v, &c);
      g[u].push_back(std::pair<int, int>(v, c));
      g[v].push_back(std::pair<int, int>(u, c));
    }
    dfs(1, 0);
    printf("%lld\n", std::max(dp[1][0], dp[1][1]));
  }
  return 0;
}
