#include <bits/stdc++.h>
using namespace std;
struct way {
  int f, t, v, nxt;
} e[500010 * 2];
int ei;
int head[500010];
void add_edge(int f, int t, int v) {
  e[++ei].f = f;
  e[ei].t = t;
  e[ei].v = v;
  e[ei].nxt = head[f];
  head[f] = ei;
}
int Q, N, K;
long long dp[500010][2];
void dfs(int x, int f) {
  long long base = 0;
  vector<int> di;
  for (int i = head[x]; i; i = e[i].nxt) {
    if (e[i].t != f) {
      dfs(e[i].t, x);
      if (dp[e[i].t][0] - dp[e[i].t][1] + e[i].v > 0)
        di.push_back(dp[e[i].t][0] - dp[e[i].t][1] + e[i].v);
      base += dp[e[i].t][1];
    }
  }
  sort(di.begin(), di.end(), greater<int>());
  dp[x][0] = dp[x][1] = base;
  for (int i = 0; i < K - 1 && i < di.size(); i++)
    dp[x][0] += di[i], dp[x][1] += di[i];
  if (K - 1 < di.size()) dp[x][1] += di[K - 1];
}
int main() {
  scanf("%d", &Q);
  while (Q--) {
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; i++) head[i] = 0, dp[i][0] = dp[i][1] = 0;
    for (int i = 1; i <= ei; i++) e[i].f = e[i].nxt = e[i].t = e[i].v = 0;
    ei = 0;
    for (int i = 1; i <= N - 1; i++) {
      int a, b, c;
      scanf("%d %d %d", &a, &b, &c);
      add_edge(a, b, c);
      add_edge(b, a, c);
    }
    dfs(1, -1);
    cout << dp[1][1] << endl;
  }
  return 0;
}
