#include <bits/stdc++.h>
using namespace std;
pair<int64_t, int64_t> get_best(
    int node, int parent, const vector<vector<pair<int, int64_t>>> &adj_list,
    const int64_t k) {
  vector<pair<int64_t, int64_t>> child_results;
  child_results.reserve(adj_list[node].size());
  for (const auto neigh : adj_list[node]) {
    if (neigh.first == parent) {
      continue;
    }
    auto result = get_best(neigh.first, node, adj_list, k);
    result.second += neigh.second;
    child_results.emplace_back(result);
  }
  sort(child_results.begin(), child_results.end(),
       [](const pair<int64_t, int64_t> &first,
          const pair<int64_t, int64_t> &second) {
         return second.second - second.first < first.second - first.first;
       });
  int64_t score_if_using_k = 0;
  int64_t score_if_using_kminus1 = 0;
  int num_colored = 0;
  for (int i = 0; i < child_results.size(); ++i) {
    if (i < k) {
      score_if_using_k +=
          std::max(child_results[i].first, child_results[i].second);
    } else {
      score_if_using_k += child_results[i].first;
    }
    if (i < k - 1) {
      score_if_using_kminus1 +=
          std::max(child_results[i].first, child_results[i].second);
    } else {
      score_if_using_kminus1 += child_results[i].first;
    }
  }
  return make_pair(score_if_using_k, score_if_using_kminus1);
}
int main(int argc, char **argv) {
  std::ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T-- > 0) {
    int n, k;
    cin >> n >> k;
    vector<vector<pair<int, int64_t>>> adj_list(n);
    for (int i = 0; i < n - 1; ++i) {
      int u, v;
      int64_t w;
      cin >> u >> v >> w;
      --u;
      --v;
      adj_list[u].emplace_back(v, w);
      adj_list[v].emplace_back(u, w);
    }
    const auto result = get_best(0, -1, adj_list, k);
    int64_t ans = max(result.first, result.second);
    cout << ans << endl;
  }
  return 0;
}
