#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 100;
long long dp[N][2];
int n, k, q;
struct Edge {
  int to, w;
};
vector<Edge> g[N];
bool cmp(Edge &a, Edge &b) {
  return a.w - dp[a.to][0] + dp[a.to][1] > b.w - dp[b.to][0] + dp[b.to][1];
}
void dfs(int u, int f) {
  for (auto e : g[u]) {
    if (e.to == f) continue;
    dfs(e.to, u);
  }
  sort(g[u].begin(), g[u].end(), cmp);
  dp[u][0] = dp[u][1] = 0;
  int c = 0;
  for (auto e : g[u]) {
    if (e.to == f) continue;
    if (e.w + dp[e.to][1] > dp[e.to][0]) {
      if (c < k - 1)
        dp[u][1] += e.w + dp[e.to][1];
      else
        dp[u][1] += dp[e.to][0];
      if (c < k)
        dp[u][0] += e.w + dp[e.to][1];
      else
        dp[u][0] += dp[e.to][0];
      c++;
    } else {
      dp[u][0] += dp[e.to][0];
      dp[u][1] += dp[e.to][0];
    }
  }
}
int main() {
  int t;
  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, w; i < n; ++i) {
      scanf("%d %d %d", &u, &v, &w);
      g[u].push_back((Edge){v, w});
      g[v].push_back((Edge){u, w});
    }
    dfs(1, -1);
    printf("%lld\n", dp[1][0]);
  }
}
