#include <bits/stdc++.h>
using namespace std;
const int maxn = 500011;
int tot, now[maxn], pre[maxn << 1], son[maxn << 1], v[maxn << 1];
void add(int a, int b, int c) {
  pre[++tot] = now[a];
  now[a] = tot;
  son[tot] = b;
  v[tot] = c;
}
void cc(int a, int b, int c) {
  add(a, b, c);
  add(b, a, c);
}
long long ans = 0;
int f[maxn], n, k;
void DFS(int x, int fa) {
  for (int p = now[x]; p; p = pre[p])
    if (son[p] != fa) DFS(son[p], x);
  static int a[maxn];
  int N = 0;
  for (int p = now[x]; p; p = pre[p])
    if (son[p] != fa) {
      if (v[p] > f[son[p]]) a[++N] = v[p] - f[son[p]];
    }
  if (N < k) {
    for (int i = 1; i <= N; ++i) ans += a[i];
    f[x] = 0;
    return;
  }
  sort(a + 1, a + N + 1, [](int a, int b) { return a > b; });
  for (int i = 1; i <= k; ++i) ans += a[i];
  f[x] = a[k];
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &k);
    tot = 0;
    for (int i = 1; i <= n; ++i) now[i] = 0;
    for (int i = 1, a, b, c; i < n; ++i)
      scanf("%d%d%d", &a, &b, &c), cc(a, b, c);
    ans = 0;
    DFS(1, 0);
    printf("%lld\n", ans);
  }
}
