#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
vector<vector<pii>> adj;
vector<array<ll, 2>> dp;
int n, k;
void dfs(int s, int p = -1) {
  ll curr = 0;
  vector<ll> add;
  for (auto it : adj[s]) {
    int to = it.first;
    int w = it.second;
    if (to == p) continue;
    dfs(to, s);
    curr += dp[to][0];
    add.push_back(dp[to][1] + w - dp[to][0]);
  }
  sort(add.begin(), add.end());
  reverse(add.begin(), add.end());
  for (int i = 0; i < min((int)add.size(), k); i++) {
    if (add[i] > 0) curr += add[i];
  }
  dp[s][0] = dp[s][1] = curr;
  if (k <= add.size() && add[k - 1] > 0) dp[s][1] -= add[k - 1];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tt;
  cin >> tt;
  while (tt--) {
    cin >> n >> k;
    adj = vector<vector<pii>>(n);
    dp = vector<array<ll, 2>>(n);
    for (int i = 0; i < n - 1; i++) {
      int x, y, w;
      cin >> x >> y >> w;
      x--, y--;
      adj[x].push_back({y, w});
      adj[y].push_back({x, w});
    }
    dfs(0);
    cout << dp[0][0] << '\n';
  }
}
