#include <bits/stdc++.h>
using namespace std;
int n, k;
struct Edge {
  int v, c, nxt;
} e[1000010];
int tot;
int first[500010];
void build(int u, int v, int c) {
  e[++tot] = (Edge){v, c, first[u]};
  first[u] = tot;
  return;
}
long long f[500010][2];
int tmp[500010];
void dfs(int u, int lst) {
  for (int i = first[u]; i; i = e[i].nxt)
    if (e[i].v != lst) dfs(e[i].v, u);
  int cnt = 0;
  long long sum = 0;
  for (int i = first[u]; i; i = e[i].nxt)
    if (e[i].v != lst) {
      int v = e[i].v;
      int c = e[i].c;
      sum += f[v][0];
      tmp[++cnt] = f[v][1] + c - f[v][0];
    }
  sort(tmp + 1, tmp + cnt + 1);
  reverse(tmp + 1, tmp + cnt + 1);
  f[u][0] = f[u][1] = sum;
  for (int i = 1; i <= min(cnt, k); i++) {
    if (tmp[i] < 0) break;
    f[u][0] += tmp[i];
    if (i < k) f[u][1] += tmp[i];
  }
  return;
}
int main() {
  int q;
  scanf("%d", &q);
  while (q--) {
    scanf("%d %d", &n, &k);
    for (int i = 1; i < n; i++) {
      int u, v, c;
      scanf("%d %d %d", &u, &v, &c);
      build(u, v, c);
      build(v, u, c);
    }
    dfs(1, 0);
    printf("%I64d\n", max(f[1][0], f[1][1]));
    for (int i = 1; i <= n; i++) first[i] = 0;
    tot = 0;
  }
  return 0;
}
