#include <bits/stdc++.h>
using namespace std;
using edgevec = vector<vector<pair<int, long long>>>;
pair<long long, long long> dfs(int curr, int prev, int k, edgevec &e) {
  vector<long long> v;
  long long all = 0;
  for (auto &iter : e[curr]) {
    auto to = iter.first;
    if (prev == to) continue;
    auto w = iter.second;
    auto d = dfs(to, curr, k, e);
    all += d.first;
    if (w - d.second > 0) v.emplace_back(w - d.second);
  }
  sort(v.rbegin(), v.rend());
  for (int i = 0; i < min((int)v.size(), k); i++) {
    all += v[i];
  }
  long long next = 0;
  if (v.size() >= k) next = v[k - 1];
  return {all, next};
}
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int q;
  cin >> q;
  while (q--) {
    int n, k;
    cin >> n >> k;
    edgevec e(n);
    for (int i = 0; i < n - 1; i++) {
      int u, v;
      long long w;
      cin >> u >> v >> w;
      u--;
      v--;
      e[u].emplace_back(v, w);
      e[v].emplace_back(u, w);
    }
    auto ans = dfs(0, -1, k, e);
    cout << ans.first << "\n";
  }
  return 0;
}
