#include <bits/stdc++.h>
using namespace std;
void solve();
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  long long q;
  cin >> q;
  for (long long(qwe) = 0; (qwe) < (q); ++(qwe)) solve();
}
struct edge {
  long long to, w;
};
vector<vector<edge>> g;
vector<long long> dp0, dp1;
long long k;
void dfs(long long v, long long p = -1) {
  vector<edge> son;
  for (auto u : g[v]) {
    if (u.to != p) {
      dfs(u.to, v);
      son.push_back(u);
    }
  }
  vector<long long> to_dp_0;
  long long tdp0 = 0;
  for (auto u : son) {
    to_dp_0.push_back(dp1[u.to] + u.w - dp0[u.to]);
    tdp0 += dp0[u.to];
  }
  sort((to_dp_0).begin(), (to_dp_0).end());
  reverse((to_dp_0).begin(), (to_dp_0).end());
  to_dp_0.resize(min((long long)(to_dp_0).size(), k));
  while (!to_dp_0.empty() && to_dp_0.back() < 0) to_dp_0.pop_back();
  for (auto u : to_dp_0) tdp0 += u;
  dp0[v] = tdp0;
  vector<long long> to_dp_1;
  long long tdp1 = 0;
  for (auto u : son) {
    to_dp_1.push_back(dp1[u.to] + u.w - dp0[u.to]);
    tdp1 += dp0[u.to];
  }
  sort((to_dp_1).begin(), (to_dp_1).end());
  reverse((to_dp_1).begin(), (to_dp_1).end());
  to_dp_1.resize(min((long long)(to_dp_1).size(), k - 1));
  while (!to_dp_1.empty() && to_dp_1.back() < 0) to_dp_1.pop_back();
  for (auto u : to_dp_1) tdp1 += u;
  dp1[v] = tdp1;
}
void solve() {
  g.resize(0);
  dp0.resize(0);
  dp1.resize(0);
  long long n;
  cin >> n >> k;
  g.resize(n);
  dp0.resize(n);
  dp1.resize(n);
  for (long long(qwe) = 0; (qwe) < (n - 1); ++(qwe)) {
    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);
  cout << max(dp0[0], dp1[0]) << '\n';
}
