#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int mod0 = 1e9 + 7;
const long long mod1 = 998244353;
const long long mod2 = 1e9 + 9;
const long long mod3 = 2147483647;
const int sz = 256 * 1024;
const long long inf = 2 * 1024 * 1024 * 1023 - 1;
const long long INF = inf * inf;
const double eps = 1e-6;
void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
int k;
void dfs(int v, vector<vector<pair<long long, long long> > > &g,
         vector<long long> &dp1, vector<long long> &dp2, int p = -1) {
  long long w0 = 0;
  vector<long long> w;
  long long sum = 0;
  for (pair<long long, long long> u : g[v]) {
    if (u.first == p) {
      w0 = u.second;
      continue;
    }
    dfs(u.first, g, dp1, dp2, v);
    sum += dp1[u.first];
    w.push_back(dp2[u.first] - dp1[u.first]);
  }
  sort((w).begin(), (w).end()), reverse((w).begin(), (w).end());
  int m = w.size();
  for (int i = 0; i < min(m, k - 1); ++i) {
    if (w[i] > 0) sum += w[i];
  }
  dp2[v] = sum + w0;
  dp1[v] = sum;
  if (k - 1 < m) dp1[v] += max(0ll, w[k - 1]);
}
void solve() {
  int n;
  cin >> n >> k;
  vector<vector<pair<long long, long long> > > g(n);
  vector<long long> dp1(n), dp2(n);
  for (int i = 1; i < n; ++i) {
    int v, u, w;
    cin >> v >> u >> w;
    v--, u--;
    g[v].push_back({u, w});
    g[u].push_back({v, w});
  }
  dfs(0, g, dp1, dp2);
  cout << dp1[0] << '\n';
}
bool multitest = true;
int main() {
  init();
  int t = 1;
  if (multitest) cin >> t;
  for (int i = 0; i < t; ++i) solve();
  return 0;
}
