#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
long long n, k;
vector<pair<long long, long long>> adj[505050];
map<pair<long long, long long>, long long> M;
long long dfs(long long i, long long p, long long w) {
  if (M.count({i, w})) return M[{i, w}];
  vector<pair<long long, long long>> I;
  for (pair<long long, long long> jw : adj[i]) {
    long long j = jw.first;
    long long w = jw.second;
    if (j != p) {
      I.push_back({w + dfs(j, i, 1), dfs(j, i, 0)});
    }
  }
  sort(I.begin(), I.end(),
       [&](pair<long long, long long> v1, pair<long long, long long> v2) {
         return v1.first - v1.second > v2.first - v2.second;
       });
  long long id = min(k - w - 1, (long long)I.size() - 1);
  while (id >= 0 && I[id].first - I[id].second <= 0) id--;
  long long r = 0;
  for (long long i = 0; i <= id; i++) r += I[i].first;
  for (long long i = id + 1; i < I.size(); i++) r += I[i].second;
  return M[{i, w}] = r;
}
int main() {
  ios_base::sync_with_stdio(false);
  long long q;
  cin >> q;
  while (q--) {
    M.clear();
    cin >> n >> k;
    for (long long i = 1; i < n; i++) {
      long long u, v, w;
      cin >> u >> v >> w;
      adj[u].push_back({v, w});
      adj[v].push_back({u, w});
    }
    cout << dfs(1, 1, 0) << "\n";
    for (long long i = 1; i <= n; i++) adj[i].clear();
  }
}
