#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 5e5 + 239;
long long solve_op(vector<pair<long long, long long>> op, long long k) {
  long long ans = 0;
  vector<long long> df;
  for (auto [f, s] : op) {
    ans += s;
    df.push_back(f - s);
  }
  sort(df.rbegin(), df.rend());
  for (long long i = 0; i < min((long long)op.size(), k); i++) {
    ans += max((long long)0, df[i]);
  }
  return ans;
}
long long n, k;
vector<vector<pair<long long, long long>>> g;
long long dp[MAXN][2];
long long used[MAXN];
void dfs(long long cur) {
  used[cur] = 1;
  vector<pair<long long, long long>> op;
  for (auto [t, w] : g[cur]) {
    if (!used[t]) {
      dfs(t);
      dp[cur][0] += dp[t][0];
      dp[cur][1] += dp[t][0];
      long long diff = dp[t][1] - dp[t][0];
      op.push_back({w, diff});
    }
  }
  dp[cur][0] += solve_op(op, k - 1);
  dp[cur][1] += solve_op(op, k);
}
void solve() {
  g.clear();
  cin >> n >> k;
  g.resize(n);
  for (long long i = 0; i < n; i++) {
    dp[i][0] = 0;
    dp[i][1] = 0;
    used[i] = 0;
  }
  for (long long i = 0; i + 1 < n; i++) {
    long long u, v, w;
    cin >> u >> v >> w;
    u--;
    v--;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  dfs(0);
  cout << max(dp[0][0], dp[0][1]) << '\n';
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  long long q;
  cin >> q;
  while (q--) {
    solve();
  }
}
