#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<long long, long long>>> a;
vector<pair<long long, long long>> ans;
vector<multiset<long long>> st;
long long k;
long long get(long long u, long long v, long long w) {
  if (a[v].size() <= k)
    return ans[v].first + w;
  else
    return max(ans[v].first, ans[v].second + w);
}
void dfs(long long v, long long p) {
  st[v].clear();
  for (auto i : a[v]) {
    if (i.first == p) continue;
    dfs(i.first, v);
    ans[v].first += ans[i.first].first;
    ans[v].second += ans[i.first].first;
    st[v].insert(min(0ll, -get(v, i.first, i.second) + ans[i.first].first));
  }
  long long kolvo = 0;
  for (auto i : st[v]) {
    if (kolvo == k) break;
    ans[v].first -= i;
    if (kolvo < k - 1) ans[v].second -= i;
    kolvo++;
  }
}
void solve() {
  long long n;
  cin >> n >> k;
  a.resize(n, vector<pair<long long, long long>>(0));
  for (long long i = 0; i < n; i++) a[i].clear();
  for (long long i = 1; i < n; i++) {
    long long u, v, w;
    cin >> u >> v >> w;
    u--;
    v--;
    a[u].push_back({v, w});
    a[v].push_back({u, w});
  }
  ans.resize(n, {0, 0});
  st.resize(n);
  for (long long i = 0; i < n; i++) {
    ans[i] = {0, 0};
  }
  dfs(0, 0);
  cout << ans[0].first << '\n';
}
int32_t main() {
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  cout.tie(NULL);
  long long q;
  cin >> q;
  for (long long i = 0; i < q; i++) {
    solve();
  }
  return 0;
}
