#include <bits/stdc++.h>
using namespace std;
vector<int> E[555555], W[555555];
vector<long long> G[555555];
int T, N, K, A[555555];
long long F[555555][2];
void dfs(int x, int f) {
  F[x][1] = 0;
  F[x][0] = 0;
  int cnt = E[x].size();
  for (int i = 0; i < cnt; i++) {
    int nx = E[x][i];
    if (nx != f) {
      dfs(nx, x);
      int w = W[x][i];
      G[x].push_back(w + F[nx][1] - F[nx][0]);
      F[x][0] += F[nx][0];
      F[x][1] += F[nx][0];
    }
  }
  if (f) {
    cnt--;
  }
  sort(G[x].begin(), G[x].end());
  for (int i = cnt - 1; i >= 0 && cnt - i < K; i--) {
    if (G[x][i] > 0) {
      F[x][1] += G[x][i];
    }
  }
  for (int i = cnt - 1; i >= 0 && cnt - i <= K; i--) {
    if (G[x][i] > 0) {
      F[x][0] += G[x][i];
    }
  }
}
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &N, &K);
    for (int i = 1; i < N; i++) {
      int u, v, w;
      scanf("%d%d%d", &u, &v, &w);
      E[u].push_back(v);
      E[v].push_back(u);
      W[u].push_back(w);
      W[v].push_back(w);
    }
    dfs(1, 0);
    printf("%lld\n", F[1][0]);
    for (int i = 1; i <= N; i++) {
      E[i].resize(0);
      W[i].resize(0);
      G[i].resize(0);
    }
  }
  return 0;
}
