#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
struct edge {
  int fr;
  int to;
  long long val;
  int nex;
} e[maxn << 1];
int head[maxn], cnt, n, k;
long long dp[2][maxn], ans;
void adde(int x, int y, long long z) {
  e[cnt].fr = x;
  e[cnt].to = y;
  e[cnt].val = z;
  e[cnt].nex = head[x];
  head[x] = cnt++;
}
void dfs(int u, int f) {
  priority_queue<long long> pq;
  long long x = 0;
  for (int i = head[u]; i != -1; i = e[i].nex) {
    int v = e[i].to;
    if (v == f) continue;
    dfs(v, u);
    x += dp[0][v];
    if (dp[1][v] + e[i].val - dp[0][v] > 0)
      pq.push({dp[1][v] + e[i].val - dp[0][v]});
  }
  int w = 1;
  while (!pq.empty() && w < k) {
    long long xx = pq.top();
    pq.pop();
    x += xx;
    w++;
  }
  dp[0][u] = dp[1][u] = x;
  if (!pq.empty()) dp[0][u] += pq.top();
  ans = max(ans, max(dp[1][u], dp[0][u]));
}
int main() {
  int q;
  scanf("%d", &q);
  while (q--) {
    cnt = 0;
    ans = 0;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
      head[i] = -1;
      dp[0][i] = dp[1][i] = 0;
    }
    for (int i = 1; i < n; i++) {
      int a, b;
      long long c;
      scanf("%d%d%lld", &a, &b, &c);
      adde(a, b, c);
      adde(b, a, c);
    }
    dfs(1, 0);
    printf("%lld\n", ans);
  }
  return 0;
}
