#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
const int N = (int)2e6 + 5;
int n, k, q;
long long dp[2][N];
int b[N], v[N], c[N], f[N], tot;
void add(int x, int y, int z) {
  v[++tot] = y, c[tot] = z, f[tot] = b[x], b[x] = tot;
}
long long tmp[N];
int top;
void dfs(int x, int fa) {
  dp[0][x] = dp[1][x] = 0;
  for (int i = b[x]; i; i = f[i])
    if (v[i] != fa) {
      dfs(v[i], x);
    }
  top = 0;
  for (int i = b[x]; i; i = f[i])
    if (v[i] != fa) {
      dp[0][x] += dp[1][v[i]];
      tmp[++top] = dp[0][v[i]] - dp[1][v[i]] + c[i];
    }
  sort(tmp + 1, tmp + top + 1);
  reverse(tmp + 1, tmp + top + 1);
  dp[1][x] = dp[0][x];
  for (int i = 1; i <= min(top, k - 1); ++i)
    if (tmp[i] > 0) dp[0][x] += tmp[i];
  for (int i = 1; i <= min(top, k); ++i)
    if (tmp[i] > 0) dp[1][x] += tmp[i];
}
int main() {
  for (scanf("%d", &q); q--;) {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) b[i] = 0;
    tot = 0;
    for (int i = 1; i <= n - 1; ++i) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      add(x, y, z), add(y, x, z);
    }
    dfs(1, 0);
    printf("%lld\n", max(dp[0][1], dp[1][1]));
  }
  return 0;
}
