#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
const int inf = 0x3f3f3f3f;
int kase, n, k;
struct Edge {
  int to, nex;
  long long val;
} edge[maxn << 1];
int head[maxn], ecnt;
void add_edge(int u, int v, long long val) {
  edge[++ecnt] = {v, head[u], val};
  head[u] = ecnt;
}
long long dp[maxn][2];
void init() {
  ecnt = 0;
  for (int i = 1; i <= n; i++) head[i] = 0, dp[i][1] = dp[i][0] = 0;
}
void dfs(int now, int fa) {
  long long cur = 0;
  vector<long long> adds;
  for (int i = head[now]; i; i = edge[i].nex) {
    int to = edge[i].to;
    long long val = edge[i].val;
    if (to == fa) continue;
    dfs(to, now);
    cur += dp[to][0];
    adds.push_back(dp[to][1] + val - dp[to][0]);
  }
  sort(adds.begin(), adds.end(), greater<long long>());
  int sz = adds.size();
  for (int i = 0; i < min(sz, k); i++)
    if (adds[i] > 0) cur += adds[i];
  dp[now][0] = dp[now][1] = cur;
  if (k <= sz && adds[k - 1] > 0) dp[now][1] -= adds[k - 1];
}
int main() {
  scanf("%d", &kase);
  while (kase--) {
    scanf("%d %d", &n, &k);
    init();
    for (int i = 1; i < n; i++) {
      int u, v;
      long long val;
      scanf("%d %d %lld", &u, &v, &val);
      add_edge(u, v, val);
      add_edge(v, u, val);
    }
    dfs(1, 0);
    printf("%lld\n", dp[1][0]);
  }
  return 0;
}
