#include <bits/stdc++.h>
using namespace std;
const int twx = 500005;
const int inf = 0x3f3f3f3f;
long long read() {
  long long sum = 0;
  long long flag = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') {
      flag = -1;
    }
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    sum = ((sum * 10) + c - '0');
    c = getchar();
  }
  return sum * flag;
}
long long n, k;
struct LV {
  int Next;
  int y;
  int v;
} a[twx << 1];
int Link[twx];
long long asd[twx];
int len;
long long g[twx];
long long st[twx];
long long top;
int t;
void Insert(int x, int y, int z) {
  a[++len].y = y;
  a[len].v = z;
  a[len].Next = Link[x];
  Link[x] = len;
}
void clean() {
  len = 0;
  for (int i = 1; i <= n; i++) {
    Link[i] = asd[i] = g[i] = 0;
  }
}
void dfs(int x, int fa) {
  for (int i = Link[x]; i; i = a[i].Next) {
    int y = a[i].y;
    if (y == fa) {
      continue;
    }
    dfs(y, x);
  }
  top = 0;
  long long sum = 0;
  for (int i = Link[x]; i; i = a[i].Next) {
    int y = a[i].y;
    int v = a[i].v;
    if (y == fa) {
      continue;
    }
    long long d = asd[y] + v - g[y];
    st[++top] = d;
    sum += g[y];
  }
  sort(st + 1, st + top + 1, greater<long long>());
  g[x] = asd[x] = sum;
  for (int i = 1; i <= k && i <= top; i++) {
    if (st[i] <= 0) {
      break;
    }
    g[x] += st[i];
    if (i <= k - 1) {
      asd[x] += st[i];
    }
  }
}
void init() {
  t = read();
  while (t--) {
    n = read();
    k = read();
    clean();
    for (int i = 1; i <= n - 1; i++) {
      int x = read();
      int y = read();
      int z = read();
      Insert(x, y, z);
      Insert(y, x, z);
    }
    dfs(1, 0);
    printf("%lld\n", g[1]);
  }
}
int main() {
  init();
  return 0;
}
