#include <bits/stdc++.h>
using namespace std;
int const N = 500050;
vector<pair<int, int>> adj[N];
long long dp[N][2];
int n, k;
struct aux {
  long long dif, z, u;
};
bool comp(aux a, aux b) { return a.dif > b.dif; }
void solve(int v, int p) {
  for (pair<int, int> filho : adj[v]) {
    if (filho.second != p)
      solve(filho.second, v);
    else
      dp[v][0] = filho.first;
  }
  vector<aux> temp;
  for (pair<int, int> f : adj[v]) {
    int filho = f.second;
    if (filho == p) continue;
    temp.push_back({dp[filho][0] - dp[filho][1], dp[filho][0], dp[filho][1]});
  }
  sort(temp.begin(), temp.end(), comp);
  int j = 0;
  for (int i = 0, us = 0; i < temp.size() && us < k; i++, j++, us++) {
    if (temp[i].dif <= 0) break;
    dp[v][1] += temp[i].z;
  }
  for (; j < temp.size(); j++) {
    dp[v][1] += temp[j].u;
  }
  j = 0;
  for (int i = 0, us = 0; i < temp.size() && us < k - 1; i++, j++, us++) {
    if (temp[i].dif <= 0) break;
    dp[v][0] += temp[i].z;
  }
  for (; j < temp.size(); j++) {
    dp[v][0] += temp[j].u;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
      adj[i].clear();
      dp[i][0] = dp[i][1] = 0;
    }
    for (int i = 1; i < n; i++) {
      int u, v, w;
      cin >> u >> v >> w;
      adj[u].push_back({w, v});
      adj[v].push_back({w, u});
    }
    solve(1, 0);
    for (int i = 1; i <= n; i++) {
    }
    cout << dp[1][1] << endl;
  }
}
