#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<vector<pair<int, long long>>> g;
pair<long long, long long> dp(int v, int p) {
  int sz = g[v].size();
  vector<pair<long long, pair<long long, long long>>> ans;
  for (auto t : g[v]) {
    if (t.first != p) {
      auto t1 = dp(t.first, v);
      ans.push_back(
          {t1.first + t.second - t1.second, {t1.first + t.second, t1.second}});
    }
  }
  sort(ans.rbegin(), ans.rend());
  pair<long long, long long> rt = {0, 0};
  int sz1 = ans.size();
  int ind = min(k, sz1);
  for (int i = 0; i < min(k, sz1); i++) {
    if (ans[i].first <= 0) {
      ind = i;
      break;
    }
    rt.second += ans[i].second.first;
  }
  for (int i = ind; i < ans.size(); i++) {
    rt.second += ans[i].second.second;
  }
  ind = min(k - 1, sz1);
  for (int i = 0; i < min(k - 1, sz1); i++) {
    if (ans[i].first <= 0) {
      ind = i;
      break;
    }
    rt.first += ans[i].second.first;
  }
  for (int i = ind; i < ans.size(); i++) {
    rt.first += ans[i].second.second;
  }
  return rt;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    g.assign(n, vector<pair<int, long long>>());
    for (int i = 0; i < n - 1; i++) {
      int a, b, c;
      cin >> a >> b >> c;
      a--;
      b--;
      g[a].push_back({b, c});
      g[b].push_back({a, c});
    }
    auto t = dp(0, -1);
    cout << max(t.first, t.second) << "\n";
  }
}
