#include <bits/stdc++.h>
using namespace std;
const int MaxN = 5e5 + 55;
long long dp[MaxN][2];
vector<pair<int, int> > v[MaxN];
int n, k;
void clearAll() {
  for (int i = 1; i <= n; ++i) {
    v[i].clear();
    dp[i][0] = dp[i][1] = 0;
  }
}
void dfs(int x, int p = 0) {
  vector<long long> curV;
  for (auto e : v[x])
    if (e.first != p) {
      int to = e.first;
      dfs(to, x);
      dp[x][0] += dp[to][1];
      dp[x][1] += dp[to][1];
      curV.push_back(e.second + dp[to][0] - dp[to][1]);
    }
  sort(curV.begin(), curV.end(), greater<long long>());
  for (int i = 0; i < min(k - 1, (int)curV.size()); ++i)
    dp[x][0] += max(0ll, curV[i]);
  for (int i = 0; i < min(k, (int)curV.size()); ++i)
    dp[x][1] += max(0ll, curV[i]);
}
void solve() {
  clearAll();
  cin >> n >> k;
  for (int i = 1; i < n; ++i) {
    int x, y, z;
    cin >> x >> y >> z;
    v[x].push_back({y, z});
    v[y].push_back({x, z});
  }
  dfs(1);
  cout << dp[1][1] << '\n';
  clearAll();
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int q;
  cin >> q;
  while (q-- > 0) solve();
  return 0;
}
