#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using ll = long long;
using vll = vector<ll>;
int q, n, k;
vii g[500005];
ll dp1[500005], dp2[500005];
void dfs(int u, int p) {
  ll sum = 0;
  vector<ll> vals;
  for (auto e : g[u]) {
    int v = e.second, w = e.first;
    if (v != p) {
      dfs(v, u);
      sum += dp1[v];
      vals.push_back(1LL * w + dp2[v] - dp1[v]);
    }
  }
  sort(vals.begin(), vals.end(), greater<ll>());
  dp1[u] = dp2[u] = sum;
  for (int i = 0; i < (int)vals.size(); ++i) {
    if (vals[i] < 0) break;
    if (i < k) {
      dp1[u] += vals[i];
    }
    if (i < k - 1) {
      dp2[u] += vals[i];
    }
  }
}
int main() {
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
      g[i].clear();
    }
    for (int i = 0; i < n - 1; ++i) {
      int u, v, w;
      scanf("%d%d%d", &u, &v, &w);
      g[u].push_back({w, v});
      g[v].push_back({w, u});
    }
    dfs(1, 0);
    printf("%lld\n", dp1[1]);
  }
}
