#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<long long, long long>>> g;
vector<long long> dp[2];
long long n, k;
void dfs(long long v, long long pr) {
  vector<long long> a;
  long long sm = 0;
  for (auto p : g[v]) {
    long long u = p.first;
    long long w = p.second;
    if (u == pr) continue;
    dfs(u, v);
    sm += dp[0][u];
    a.push_back(dp[1][u] + w - dp[0][u]);
  }
  sort(a.rbegin(), a.rend());
  for (long long i = 0; i < min((long long)a.size(), k); ++i) {
    if (a[i] > 0) {
      sm += a[i];
    }
  }
  dp[0][v] = dp[1][v] = sm;
  if (k <= a.size() && a[k - 1] > 0) {
    sm -= a[k - 1];
    dp[1][v] = sm;
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long q;
  cin >> q;
  for (long long s = 0; s < q; ++s) {
    cin >> n >> k;
    g.resize(n);
    g.assign(n, vector<pair<long long, long long>>());
    dp[0].resize(n);
    dp[1].resize(n);
    dp[0].assign(n, 0);
    dp[1].assign(n, 0);
    for (long long i = 0; i < n - 1; ++i) {
      long long v, u, w;
      cin >> v >> u >> w;
      --v;
      --u;
      g[v].push_back({u, w});
      g[u].push_back({v, w});
    }
    dfs(0, -1);
    cout << dp[0][0] << '\n';
  }
}
