#include <bits/stdc++.h>
using namespace std;
const int M = 5e5 + 5;
int q, n, k;
vector<int> g[M], G[M];
long long diff[M], f[M], h[M];
long long c[M];
void dfs(int u, int F) {
  long long sum = 0;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i], w = G[u][i];
    if (v != F) {
      dfs(v, u);
      sum += f[v];
      diff[v] = f[v] - (w + h[v]);
    }
  }
  int t = 0;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i];
    if (v != F) {
      c[++t] = diff[v];
    }
  }
  sort(c + 1, c + 1 + t);
  int l = min(t, k - 1);
  for (int i = 1; i <= l; i++) {
    if (c[i] >= 0) break;
    sum -= c[i];
  }
  h[u] = sum;
  if (t >= k && c[k] < 0) {
    sum -= c[k];
  }
  f[u] = sum;
}
int main() {
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) g[i].clear(), G[i].clear();
    for (int i = 1; i < n; i++) {
      int u, v, w;
      scanf("%d%d%d", &u, &v, &w);
      g[u].push_back(v);
      g[v].push_back(u);
      G[u].push_back(w);
      G[v].push_back(w);
    }
    dfs(1, -1);
    printf("%I64d\n", f[1]);
  }
}
