#include <bits/stdc++.h>
const int kInf = 0x3f3f3f3f, kMod = 1e9 + 7;
const long long kInf64 = 0x3f3f3f3f3f3f3f3f;
template <typename T>
inline void UMin(T& x, const T& y) {
  if (x > y) x = y;
}
template <typename T>
inline void UMax(T& x, const T& y) {
  if (x < y) x = y;
}
inline int Add(int a, int b) { return (a += b) >= kMod ? a - kMod : a; }
inline int Sub(int a, int b) { return (a -= b) < 0 ? a + kMod : a; }
inline int Mul(int a, int b) { return 1ll * a * b % kMod; }
int FPow(int bs, int ex = kMod - 2) {
  int res = 1;
  for (; ex; bs = Mul(bs, bs), ex >>= 1)
    if (ex & 1) res = Mul(res, bs);
  return res;
}
void Solve();
int main() {
  int q;
  scanf("%d", &q);
  while (q--) Solve();
  return 0;
}
const int kMaxn = 5e5 + 5;
int n, k;
long long DP[kMaxn][2];
std::vector<std::pair<int, int> > G[kMaxn];
void Dfs(int u, int fa) {
  for (auto& p : G[u]) {
    if (p.first == fa) continue;
    Dfs(p.first, u);
  }
  std::vector<std::pair<long long, int> > buf;
  long long sum = 0;
  for (auto& p : G[u]) {
    if (p.first == fa) continue;
    sum += DP[p.first][0];
    buf.push_back({DP[p.first][0] - DP[p.first][1] - p.second, p.first});
  }
  std::sort(buf.begin(), buf.end());
  for (int i = 0; i + 1 < k && i < (int)buf.size(); ++i) {
    if (buf[i].first >= 0) break;
    sum -= buf[i].first;
  }
  DP[u][1] = sum;
  if (k - 1 < (int)buf.size() && buf[k - 1].first < 0) sum -= buf[k - 1].first;
  DP[u][0] = sum;
}
void Solve() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) G[i].clear();
  for (int i = 1, u, v, c; i < n; ++i) {
    scanf("%d%d%d", &u, &v, &c);
    G[u].push_back({v, c});
    G[v].push_back({u, c});
  }
  Dfs(1, 0);
  printf("%lld\n", std::max(DP[1][0], DP[1][1]));
}
