#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> adj[500009];
long long int dp[2][500009];
int n, k;
void dfs(int i, int p) {
  vector<long long int> v;
  for (auto x : adj[i])
    if (x.first != p) {
      dfs(x.first, i);
      if (dp[1][x.first] + x.second > dp[0][x.first])
        v.push_back(dp[1][x.first] + x.second - dp[0][x.first]);
      dp[0][i] += dp[0][x.first];
      dp[1][i] += dp[0][x.first];
    }
  sort(v.begin(), v.end());
  reverse(v.begin(), v.end());
  for (int j = 0; j < v.size(); j++) {
    if (j < k) dp[0][i] += v[j];
    if (j < k - 1) dp[1][i] += v[j];
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
      adj[i].clear();
      dp[0][i] = 0;
      dp[1][i] = 0;
    }
    int u, v, w;
    for (int i = 1; i < n; i++) {
      cin >> u >> v >> w;
      adj[u].push_back({v, w});
      adj[v].push_back({u, w});
    }
    dfs(1, 1);
    cout << dp[0][1] << "\n";
  }
}
