#include <bits/stdc++.h>
using namespace std;
template <class T>
T read1() {
  T t = 0;
  bool vis = 0;
  char k;
  do (k = getchar()) == '-' && (vis = 1);
  while ('0' > k || k > '9');
  while ('0' <= k && k <= '9')
    t = (t << 3) + (t << 1) + (k ^ '0'), k = getchar();
  return vis ? -t : t;
}
vector<long long> x[500005];
vector<pair<int, int> > G[500005];
int s, k;
long long dfs(int n, int f) {
  long long t = 0;
  for (int i = 0; i < G[n].size(); ++i)
    if (G[n][i].first ^ f) {
      long long o = dfs(G[n][i].first, n);
      t += o;
      x[n].back() += G[n][i].second - o;
    }
  sort(x[n].begin(), x[n].end());
  reverse(x[n].begin(), x[n].end());
  int j = 0;
  while (j + 1 < k && j < x[n].size() && x[n][j] > 0) t += x[n][j++];
  x[f].push_back(t);
  if (j < x[n].size() && x[n][j] > 0) t += x[n][j];
  return t;
}
int main() {
  for (int T = read1<int>(); T--;) {
    s = read1<int>(), k = read1<int>();
    for (int i = 0; i <= s; ++i) G[i].clear(), x[i].clear();
    for (int i = 1; i < s; ++i) {
      int u = read1<int>(), v = read1<int>(), t = read1<int>();
      G[u].push_back(make_pair(v, t));
      G[v].push_back(make_pair(u, t));
    }
    printf("%lld\n", dfs(1, 0));
  }
  return 0;
}
