#include <bits/stdc++.h>
using namespace std;
int F[1000010], N[1000010], a[1000010], c[1000010];
int n, m, k;
void add(int x, int y, int z) {
  a[++k] = y;
  c[k] = z;
  N[k] = F[x];
  F[x] = k;
}
long long f[500010][2];
void dfs(int x, int pre) {
  f[x][0] = f[x][1] = 0;
  vector<int> e;
  for (int i = F[x]; i; i = N[i])
    if (a[i] != pre) {
      dfs(a[i], x);
      f[x][0] += f[a[i]][1];
      f[x][1] += f[a[i]][1];
      int v = f[a[i]][0] - f[a[i]][1] + c[i];
      if (v > 0) e.push_back(v);
    }
  sort(e.begin(), e.end());
  reverse(e.begin(), e.end());
  for (int i = 0; i < e.size() && i < m - 1; i++) f[x][0] += e[i];
  for (int i = 0; i < e.size() && i <= m - 1; i++) f[x][1] += e[i];
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= k; i++) N[i] = 0;
    for (int i = 1; i <= n; i++) F[i] = 0;
    k = 0;
    for (int i = 1; i < n; i++) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      add(x, y, z);
      add(y, x, z);
    }
    dfs(1, 1);
    printf("%lld\n", max(f[1][0], f[1][1]));
  }
  return 0;
}
