#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 100;
long long dp[N][2];
vector<int> g[N], cst[N];
int K;
int n;
void solve(int u, int p, int par_w) {
  dp[u][1] = par_w;
  dp[u][0] = 0;
  vector<long long> add;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i], w = cst[u][i];
    if (v == p) continue;
    solve(v, u, w);
    dp[u][1] += dp[v][0];
    dp[u][0] += dp[v][0];
    if (dp[v][1] > dp[v][0]) add.push_back(dp[v][1] - dp[v][0]);
  }
  sort(add.rbegin(), add.rend());
  for (int i = 0; i < min(K, (int)add.size()); i++) dp[u][0] += add[i];
  for (int i = 0; i < min(K - 1, (int)add.size()); i++) dp[u][1] += add[i];
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int q;
  cin >> q;
  while (q--) {
    cin >> n >> K;
    for (int i = 1; i <= n; i++) {
      g[i].clear();
      cst[i].clear();
    }
    for (int i = 1; i < n; i++) {
      int u, v, w;
      cin >> u >> v >> w;
      g[u].push_back(v);
      g[v].push_back(u);
      cst[u].push_back(w);
      cst[v].push_back(w);
    }
    solve(1, -1, 0);
    long long ans = max(dp[1][0], dp[1][1]);
    cout << ans << "\n";
  }
  return 0;
}
