#include <bits/stdc++.h>
using namespace std;
using DO = double;
using LL = long long;
using VI = vector<LL>;
const int N = 5e5 + 10;
int head[N], nxt[N << 1], to[N << 1];
LL wei[N << 1];
int E;
void init(int n) {
  for (int i = 1; i <= n; i++) {
    head[i] = -1;
  }
  E = 0;
}
void add(int u, int v, int w) {
  nxt[E] = head[u];
  to[E] = v;
  wei[E] = w;
  head[u] = E++;
  nxt[E] = head[v];
  to[E] = u;
  wei[E] = w;
  head[v] = E++;
}
LL dp[N][2];
int n, k;
void dfs(int u, int fa = 0) {
  dp[u][0] = dp[u][1] = 0;
  VI vec;
  for (int e = head[u], v; ~e; e = nxt[e]) {
    v = to[e];
    if (v == fa) continue;
    dfs(v, u);
    dp[u][0] += dp[v][0];
    dp[u][1] += dp[v][0];
    if (dp[v][0] < dp[v][1] + wei[e]) {
      vec.push_back(dp[v][1] + wei[e] - dp[v][0]);
    }
  }
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());
  for (int i = 0; i < min((int)vec.size(), k); i++) {
    dp[u][0] += vec[i];
  }
  for (int i = 0; i < min((int)vec.size(), k - 1); i++) {
    dp[u][1] += vec[i];
  }
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d %d", &n, &k);
    init(n);
    for (int i = 1, u, v, w; i < n; i++) {
      scanf("%d %d %d", &u, &v, &w);
      add(u, v, w);
    }
    dfs(1);
    printf("%I64d\n", max(dp[1][0], dp[1][1]));
  }
  return 0;
}
