#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
constexpr int MAXN = 5e5 + 5;
vector<pii> tree[MAXN];
int k;
ll dp[MAXN][2];
void dfs(int u, int p) {
  vector<ll> adds;
  dp[u][0] = dp[u][1] = 0;
  for (auto& e : tree[u]) {
    int v, w;
    tie(v, w) = e;
    if (v == p) continue;
    dfs(v, u);
    dp[u][0] += dp[v][0];
    adds.push_back(w + dp[v][1] - dp[v][0]);
  }
  sort(begin(adds), end(adds), greater<ll>());
  int take = min(k, (int)adds.size());
  for (int i = 0; i < take; ++i) {
    dp[u][0] += max(0LL, adds[i]);
  }
  dp[u][1] = dp[u][0];
  if (take == k) {
    dp[u][1] -= max(0LL, adds[k - 1]);
  }
}
void solve() {
  int n;
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    tree[i].clear();
  }
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    --u;
    --v;
    tree[u].emplace_back(v, w);
    tree[v].emplace_back(u, w);
  }
  dfs(0, -1);
  cout << dp[0][0] << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int T;
  cin >> T;
  while (T-- > 0) {
    solve();
  }
  return 0;
}
