#include <bits/stdc++.h>
using namespace std;
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long T;
  cin >> T;
  while (T--) {
    long long N, K;
    cin >> N >> K;
    vector<vector<pair<long long, long long>>> L(N + 1);
    long long dp[N + 1][2];
    for (long long i = 1; i <= N; i++) {
      dp[i][0] = dp[i][1] = 0;
    }
    for (long long i = 1; i <= N - 1; i++) {
      long long a, b, c;
      cin >> a >> b >> c;
      L[a].push_back({b, c});
      L[b].push_back({a, c});
    }
    function<void(long long, long long)> DFS = [&](long long nodo,
                                                   long long padre) {
      long long cont = 0;
      vector<pair<long long, long long>> vect;
      for (auto v : L[nodo]) {
        if (v.first != padre) {
          DFS(v.first, nodo);
          cont++;
          vect.push_back(
              {dp[v.first][1] + v.second - dp[v.first][0], dp[v.first][0]});
        }
      }
      sort(vect.rbegin(), vect.rend());
      if (cont == 0) return;
      long long ttt = 0;
      for (long long i = 0; i < vect.size(); i++) {
        if (vect[i].first > 0 && ttt < K) {
          dp[nodo][0] += vect[i].first + vect[i].second;
          ttt++;
        } else {
          dp[nodo][0] += vect[i].second;
        }
      }
      ttt = 0;
      for (long long i = 0; i < vect.size(); i++) {
        if (vect[i].first > 0 && ttt < K - 1) {
          dp[nodo][1] += vect[i].first + vect[i].second;
          ttt++;
        } else {
          dp[nodo][1] += vect[i].second;
        }
      }
    };
    DFS(1, 0);
    cout << dp[1][0] << '\n';
  }
  return 0;
}
