#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
struct node {
  int v, w, next;
} edges[maxn << 2];
int head[maxn], cnt;
int n, k;
void add_edge(int u, int v, int w) {
  edges[++cnt] = {v, w, head[u]};
  head[u] = cnt;
}
long long dp[maxn][2];
void dfs(int rt, int fa) {
  vector<long long> vv;
  long long ans = 0;
  for (int i = head[rt]; i; i = edges[i].next) {
    if (edges[i].v == fa) continue;
    dfs(edges[i].v, rt);
    vv.push_back(dp[edges[i].v][0] + edges[i].w - dp[edges[i].v][1]);
    ans += dp[edges[i].v][1];
  }
  sort(vv.begin(), vv.end(), greater<long long>());
  if (k == 1) dp[rt][0] = ans;
  for (int i = 0; i < vv.size(); ++i) {
    if (i < k && vv[i] > 0) ans += vv[i];
    if (i == k - 1 - 1) dp[rt][0] = ans;
    if (i == k - 1) dp[rt][1] = ans;
  }
  if (dp[rt][0] == -1) dp[rt][0] = ans;
  if (dp[rt][1] == -1) dp[rt][1] = ans;
}
int main() {
  int q;
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d", &n, &k);
    memset(head, 0, sizeof(int) * (n + 1));
    memset(dp, -1, sizeof(long long) * (n + 1) * 2);
    cnt = 0;
    for (int i = 0, u, v, w; i < n - 1; ++i) {
      scanf("%d%d%d", &u, &v, &w);
      add_edge(u, v, w);
      add_edge(v, u, w);
    }
    dfs(1, 0);
    printf("%lld\n", max(dp[1][0], dp[1][1]));
  }
  return 0;
}
