#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, k, par[N];
int64_t f[N], g[N];
vector<pair<int, int> > ke[N];
vector<int64_t> c[N];
void dfs(int u) {
  int64_t sum = 0;
  for (auto e : ke[u])
    if (e.second != par[u]) {
      int v = e.second, w = e.first;
      par[v] = u;
      dfs(v);
      sum += f[v];
      c[u].push_back(g[v] + w - f[v]);
    }
  sort(c[u].begin(), c[u].end(), greater<int64_t>());
  for (int i = 0; i < k - 1 && i < (int)c[u].size() && c[u][i] > 0; ++i)
    sum += c[u][i];
  f[u] = g[u] = sum;
  if (k <= (int)c[u].size() && c[u][k - 1] > 0) f[u] += c[u][k - 1];
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n; ++i) {
      int u, v, w;
      scanf("%d%d%d", &u, &v, &w);
      ke[u].push_back(make_pair(w, v));
      ke[v].push_back(make_pair(w, u));
    }
    dfs(1);
    printf("%I64d\n", f[1]);
    for (int i = 1; i <= n; ++i) ke[i].clear(), c[i].clear(), par[i] = 0;
  }
}
