#include <bits/stdc++.h>
using namespace std;
const int N = int(500 * 1000 + 7);
int n, k;
vector<pair<int, int> > adj[N];
long long dp[N][2];
void dfs(int v, int p = -1) {
  vector<long long> x;
  long long curr = 0;
  for (auto it : adj[v]) {
    int to = it.first;
    int w = it.second;
    if (to == p) continue;
    dfs(to, v);
    curr += dp[to][0];
    x.push_back(dp[to][1] + w - dp[to][0]);
  }
  sort(x.begin(), x.end(), greater<long long>());
  for (int i = 0; i < min((int)x.size(), k); i++) {
    if (x[i] > 0) curr += x[i];
  }
  dp[v][0] = dp[v][1] = curr;
  if (k <= (int)x.size() && x[k - 1] > 0) dp[v][1] -= x[k - 1];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int q;
  cin >> q;
  while (q--) {
    cin >> n >> k;
    for (int i = 0; i < n; i++) adj[i].clear();
    for (int i = 0; i < n - 1; i++) {
      int u, v, w;
      cin >> u >> v >> w;
      u--;
      v--;
      adj[u].push_back({v, w});
      adj[v].push_back({u, w});
    }
    dfs(0, -1);
    cout << dp[0][0] << endl;
  }
  return 0;
}
