#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<long long, long long>>> graph;
long long k;
pair<long long, long long> dfs(long long v, long long prev) {
  vector<pair<long long, pair<long long, long long>>> childs;
  for (auto [u, w] : graph[v]) {
    if (u == prev) continue;
    auto [val1, val2] = dfs(u, v);
    val2 += w;
    childs.emplace_back(val2 - val1, make_pair(val1, val2));
  }
  sort(childs.rbegin(), childs.rend());
  long long ans1 = 0, ans2 = 0;
  for (long long i = 0; i < childs.size(); ++i) {
    if (i < k && childs[i].first > 0)
      ans1 += childs[i].second.second;
    else
      ans1 += childs[i].second.first;
    if (i < k - 1 && childs[i].first > 0)
      ans2 += childs[i].second.second;
    else
      ans2 += childs[i].second.first;
  }
  return {ans1, ans2};
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long q;
  cin >> q;
  while (q--) {
    long long n;
    cin >> n >> k;
    graph.assign(n, {});
    for (long long i = 0; i < n - 1; ++i) {
      long long v, u, w;
      cin >> v >> u >> w;
      --v, --u;
      graph[v].emplace_back(u, w);
      graph[u].emplace_back(v, w);
    }
    auto [val1, val2] = dfs(0, -1);
    cout << max(val1, val2) << '\n';
  }
  return 0;
}
