#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
template <typename... T>
void rd(T&... args) {
  ((cin >> args), ...);
}
template <typename... T>
void wr(T... args) {
  ((cout << args << " "), ...);
  cout << endl;
}
vector<vector<pii>> G;
int n, k;
pair<ll, ll> dfs(int u, int fa) {
  vector<ll> res;
  ll cur = 0;
  for (auto [w, to] : G[u]) {
    if (to == fa) continue;
    auto [yes, no] = dfs(to, u);
    cur += no;
    res.push_back(yes - no + w);
  }
  sort(res.rbegin(), res.rend());
  for (int i = 0; i < int(min(int(res.size()), k)); ++i)
    if (res[i] > 0) cur += res[i];
  ll yes = cur, no = cur;
  if (k <= int(res.size()) && res[k - 1] > 0) yes -= res[k - 1];
  return {yes, no};
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt;
  cin >> tt;
  while (tt--) {
    cin >> n >> k;
    G = vector<vector<pii>>(n + 1);
    for (int i = 0; i < int(n - 1); ++i) {
      int u, v, w;
      rd(u, v, w);
      G[u].emplace_back(w, v);
      G[v].emplace_back(w, u);
    }
    auto [_, ans] = dfs(1, 0);
    cout << ans << endl;
  }
  return 0;
}
