#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > g[500100];
long long f[500100][2];
int n, k;
void dfs(int u, int fa) {
  vector<long long> d;
  d.clear();
  f[u][0] = f[u][1] = 0;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i].first, w = g[u][i].second;
    if (v == fa) continue;
    dfs(v, u);
    f[u][0] += f[v][1];
    f[u][1] += f[v][1];
    d.push_back(-(w + f[v][0] - f[v][1]));
  }
  sort(d.begin(), d.end());
  for (int i = 0; i < d.size() && i < k; i++) {
    long long D = -d[i];
    if (D <= 0) break;
    if (i < k - 1) f[u][0] += D;
    f[u][1] += D;
  }
}
void ae(int x, int y, int z) { g[x].push_back(make_pair(y, z)); }
void solve() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) g[i].clear();
  int x, y, z;
  for (int i = 1; i < n; i++) {
    scanf("%d%d%d", &x, &y, &z);
    ae(x, y, z);
    ae(y, x, z);
  }
  dfs(1, 0);
  printf("%lld\n", f[1][1]);
}
int main() {
  int tc;
  scanf("%d", &tc);
  while (tc--) solve();
  return 0;
}
