#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
const int M = 1000010;
int q, n, k, cnt;
int first[N], to[M], nxt[M], val[M], fa[N], son[N];
long long f[N][2], tmp[N];
void add(int a, int b, int c) {
  to[++cnt] = b, nxt[cnt] = first[a];
  first[a] = cnt, val[cnt] = c;
  return;
}
void dfs(int x) {
  son[x] = 0;
  for (int i = first[x]; i; i = nxt[i]) {
    if (to[i] == fa[x]) continue;
    fa[to[i]] = x, son[x]++;
    dfs(to[i]);
  }
  if (!son[x])
    f[x][0] = f[x][1] = 0;
  else {
    int tcnt = 0;
    long long tot = 0;
    f[x][0] = f[x][1] = 0;
    for (int i = first[x]; i; i = nxt[i]) {
      if (to[i] == fa[x]) continue;
      tmp[++tcnt] = f[to[i]][1] + val[i] - f[to[i]][0];
      f[x][1] += f[to[i]][0];
    }
    sort(tmp + 1, tmp + 1 + tcnt, greater<int>());
    for (int i = 1; i <= tcnt && i < k; i++) {
      if (tmp[i] < 0) break;
      f[x][1] += tmp[i];
    }
    f[x][0] = f[x][1];
    if (k <= tcnt && tmp[k] > 0) f[x][0] += tmp[k];
  }
  return;
}
int main() {
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d", &n, &k), cnt = 0;
    for (int i = 1; i <= n; i++) first[i] = 0;
    for (int a, b, c, i = 1; i < n; i++) {
      scanf("%d%d%d", &a, &b, &c);
      add(a, b, c), add(b, a, c);
    }
    dfs(1);
    printf("%lld\n", max(f[1][0], f[1][1]));
  }
  return 0;
}
