#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
struct ee {
  int v;
  int w;
  int nxt;
} e[N << 1];
int h[N], et = 0;
inline void Eadd(int U, int V, int W) {
  e[++et] = (ee){V, W, h[U]};
  h[U] = et;
}
inline void add(int U, int V, int W) {
  Eadd(U, V, W);
  Eadd(V, U, W);
}
int n, K;
long long f[N][2];
long long st[N];
int tp = 0;
inline bool cmp(int A, int B) { return A > B; }
inline void dfs(int X, int FA) {
  for (int i = h[X]; i; i = e[i].nxt) {
    if (e[i].v == FA) {
      continue;
    }
    dfs(e[i].v, X);
  }
  int nw = K;
  tp = 0;
  for (int i = h[X]; i; i = e[i].nxt) {
    if (e[i].v == FA) {
      continue;
    }
    f[X][0] += f[e[i].v][1];
    st[++tp] = f[e[i].v][0] + e[i].w - f[e[i].v][1];
  }
  f[X][1] = f[X][0];
  std::sort(st + 1, st + 1 + tp, cmp);
  for (int i = 1; i <= min(tp, K); ++i) {
    if (i <= K - 1 && st[i] > 0) {
      f[X][0] += st[i];
    }
    if (i <= K && st[i] > 0) {
      f[X][1] += st[i];
    }
  }
}
void init() {
  scanf("%d%d", &n, &K);
  int u, v, w;
  for (int i = 1; i < n; ++i) {
    scanf("%d%d%d", &u, &v, &w);
    add(u, v, w);
  }
  dfs(1, 0);
  printf("%lld\n", max(f[1][0], f[1][1]));
  et = 0;
  for (int i = 1; i <= n; ++i) {
    h[i] = 0;
    f[i][0] = f[i][1] = 0;
  }
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    init();
  }
  return 0;
}
