#include <bits/stdc++.h>
using namespace std;
const long long N = 5 * 1e5 + 100;
long long t, n, k, dp[N][2];
long long tot, first[N], nxt[N * 2], point[N * 2], len[N * 2];
struct node {
  long long a, b, kind;
};
bool cmp(node a, node b) {
  return (max(a.a, a.b) > max(b.a, b.b) ||
          (max(a.a, a.b) == max(b.a, b.b) && a.kind < b.kind));
}
void add_edge(long long x, long long y, long long z) {
  tot++;
  nxt[tot] = first[x];
  first[x] = tot;
  point[tot] = y;
  len[tot] = z;
}
void dfs(long long x, long long fa) {
  vector<long long> p;
  p.clear();
  long long sum = 0;
  for (long long i = first[x]; i != -1; i = nxt[i]) {
    long long u = point[i];
    if (u == fa) continue;
    dfs(u, x);
    sum += dp[u][1];
    p.push_back(dp[u][0] + len[i] - dp[u][1]);
  }
  sort(p.begin(), p.end());
  reverse(p.begin(), p.end());
  long long tot = 0;
  dp[x][0] = max(dp[x][0], sum);
  for (long long i = 0; i < (long long)p.size(); i++) {
    tot += p[i];
    if (i + 1 == k) {
      dp[x][1] = sum + tot;
      break;
    }
    dp[x][0] = max(dp[x][0], sum + tot);
  }
  dp[x][1] = max(dp[x][0], dp[x][1]);
}
signed main() {
  scanf("%lld", &t);
  while (t--) {
    scanf("%lld%lld", &n, &k);
    tot = -1;
    for (long long i = 1; i <= n; i++) first[i] = -1;
    for (long long i = 1; i < n; i++) {
      long long u, v, w;
      scanf("%lld%lld%lld", &u, &v, &w);
      add_edge(u, v, w);
      add_edge(v, u, w);
    }
    for (long long i = 1; i <= n; i++) dp[i][0] = dp[i][1] = 0;
    dfs(1, 1);
    long long ans = 0;
    for (long long i = 1; i <= n; i++) ans = max(ans, max(dp[i][0], dp[i][1]));
    printf("%lld\n", ans);
  }
}
