#include <bits/stdc++.h>
using namespace std;
void read(int &n) {
  int c;
  for (n = 0; (c = getchar()) > 57 || c < 48;)
    ;
  for (; c > 47 && c < 58; c = getchar()) n = n * 10 + c - 48;
}
int n, k, fir[500100], nex[500100 + 500100], to[500100 + 500100], top,
    e[500100 + 500100];
long long f[500100][2], a[500100];
void dfs(int x, int fa) {
  long long sm = 0, s = 0;
  int T = 0;
  for (int i = fir[x]; i; i = nex[i])
    if (to[i] ^ fa) dfs(to[i], x);
  for (int i = fir[x]; i; i = nex[i])
    if (to[i] ^ fa) {
      int y = to[i];
      sm += f[y][1];
      a[++T] = f[y][0] + e[i] - f[y][1];
    }
  sort(a + 1, a + T + 1);
  for (int i = 1; i < k && i <= T; ++i) s += max(a[T + 1 - i], 0ll);
  f[x][0] = sm + s;
  if (k <= T) s += max(a[T + 1 - k], 0ll);
  f[x][1] = sm + s;
}
int main() {
  int _;
  scanf("%d", &_);
  while (_--) {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) fir[i] = 0, f[i][0] = f[i][1] = 0;
    top = 0;
    for (int i = 1; i < n; ++i) {
      int x, y, v;
      read(x);
      read(y);
      read(v);
      to[++top] = y, nex[top] = fir[x], fir[x] = top, e[top] = v;
      to[++top] = x, nex[top] = fir[y], fir[y] = top, e[top] = v;
    }
    dfs(1, 0);
    printf("%I64d\n", max(f[1][0], f[1][1]));
  }
}
