#include <bits/stdc++.h>
using namespace std;
struct Edge {
  int val, to, nxt;
} edge[2 * 500005];
int head[500005];
int tot = 0;
int n, k;
void init() {
  for (int i = 1; i <= n; i++) {
    head[i] = -1;
  }
  tot = 0;
}
void addedge(int u, int v, int value) {
  edge[tot].nxt = head[u];
  head[u] = tot;
  edge[tot].to = v;
  edge[tot++].val = value;
}
long long dp[500005][2];
void dfs(int u, int fa) {
  dp[u][0] = dp[u][1] = 0;
  vector<int> res;
  for (int i = head[u]; i != -1; i = edge[i].nxt) {
    int v = edge[i].to;
    if (v == fa) continue;
    dfs(v, u);
    res.push_back(dp[v][1] + edge[i].val - dp[v][0]);
    dp[u][0] += dp[v][0];
    dp[u][1] += dp[v][0];
  }
  sort(res.begin(), res.end(), greater<int>());
  int cnt = 0;
  int sz = res.size();
  for (int i = 0; i < sz; i++) {
    if (cnt == k || res[i] <= 0) break;
    dp[u][0] += res[i];
    if (cnt != k - 1) dp[u][1] += res[i];
    cnt++;
  }
}
int main() {
  int cas;
  scanf("%d", &cas);
  while (cas--) {
    scanf("%d%d", &n, &k);
    init();
    for (int i = 1; i < n; i++) {
      int u, v, value;
      scanf("%d%d%d", &u, &v, &value);
      addedge(u, v, value);
      addedge(v, u, value);
    }
    dfs(1, 0);
    printf("%lld\n", max(dp[1][0], dp[1][1]));
  }
}
