#include <bits/stdc++.h>
using namespace std;
struct {
  int v, w, next;
} edge[1000010];
int head[500010], cnt;
void add(int u, int v, int w) {
  edge[cnt].v = v;
  edge[cnt].w = w;
  edge[cnt].next = head[u];
  head[u] = cnt++;
}
long long dp[500010][2];
void dfs(int k, int fz, int z) {
  dp[k][0] = 0;
  dp[k][1] = 0;
  priority_queue<long long> q;
  long long sum = 0;
  for (int i = head[k]; i != -1; i = edge[i].next) {
    int v = edge[i].v;
    int w = edge[i].w;
    if (v != fz) {
      dfs(v, k, z);
      sum += dp[v][0];
      q.push(dp[v][1] - dp[v][0] + w);
    }
  }
  z--;
  bool lg = true;
  while (lg && !q.empty() && z) {
    long long a = q.top();
    q.pop();
    if (a <= 0)
      lg = false;
    else
      sum += a;
    z--;
  }
  dp[k][1] = sum;
  if (lg && !q.empty()) {
    long long a = q.top();
    q.pop();
    if (a > 0) sum += a;
  }
  dp[k][0] = sum;
  return;
}
int main() {
  int q;
  scanf("%d", &q);
  while (q--) {
    cnt = 0;
    int n, k;
    scanf("%d%d", &n, &k);
    fill(head, head + n + 3, -1);
    int u, v, w;
    for (int i = 1; i < n; i++) {
      scanf("%d%d%d", &u, &v, &w);
      add(u, v, w);
      add(v, u, w);
    }
    dfs(1, 0, k);
    printf("%lld\n", dp[1][0]);
  }
  return 0;
}
