#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int getrnd(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
template <typename T1, typename T2>
bool relax(T1& a, T2 b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T1, typename T2>
bool strain(T1& a, T2 b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
int n, k;
vector<int> was;
vector<vector<ll>> dp;
vector<list<pair<int, int>>> graph;
void dfs(int v, int p = -1) {
  if (was[v]) return;
  was[v] = 1;
  ll s = 0;
  vector<ll> diff;
  for (const auto& i : graph[v]) {
    if (i.first == p) continue;
    dfs(i.first, v);
    diff.emplace_back(dp[i.first][1] + i.second - dp[i.first][0]);
    s += dp[i.first][0];
  }
  sort(diff.rbegin(), diff.rend());
  for (int i = 0; i < min((int)diff.size(), k) && diff[i] > 0; ++i)
    s += diff[i];
  dp[v][0] = dp[v][1] = s;
  if (k <= diff.size() && diff[k - 1] > 0) dp[v][1] -= diff[k - 1];
}
void solve() {
  cin >> n >> k;
  graph.resize(n);
  for (int i = 0; i < n; ++i) graph[i].clear();
  for (int i = 0; i < n - 1; ++i) {
    int v, t, w;
    cin >> v >> t >> w;
    graph[v - 1].emplace_back(t - 1, w);
    graph[t - 1].emplace_back(v - 1, w);
  }
  was.assign(n, 0);
  dp.assign(n, vector<ll>(2, 0));
  dfs(0);
  cout << dp[0][0] << '\n';
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}
