#include <bits/stdc++.h>
using namespace std;
long long dp[500005][2];
int v[500005], u[500005], w[500005];
vector<int> adj[500005];
int k;
priority_queue<long long> pq[500005];
void dfs(int v, int p) {
  dp[v][0] = dp[v][1] = 0;
  for (int& x : adj[v]) {
    int u = ::v[x] + ::u[x] - v;
    if (u == p) continue;
    dfs(u, v);
    dp[v][0] += dp[u][0];
    pq[v].push(w[x] + dp[u][1] - dp[u][0]);
  }
  int t = k - 1;
  while (!pq[v].empty() && t) {
    if (pq[v].top() < 0) break;
    dp[v][0] += pq[v].top();
    pq[v].pop();
    t--;
  }
  dp[v][1] = dp[v][0];
  if (!pq[v].empty()) {
    if (pq[v].top() > 0) {
      dp[v][0] += pq[v].top();
    }
  }
  while (!pq[v].empty()) pq[v].pop();
}
void go() {
  int n;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) adj[i].clear();
  for (int i = 1; i < n; i++) {
    cin >> v[i] >> u[i] >> w[i];
    adj[v[i]].push_back(i);
    adj[u[i]].push_back(i);
  }
  dfs(1, 0);
  cout << max(dp[1][0], dp[1][1]) << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  int t;
  cin >> t;
  while (t--) {
    go();
  }
}
