#include <bits/stdc++.h>
namespace OI {
template <class T>
void rd(T &x) {
  x = 0;
  int f = 1;
  char c;
  while (!isdigit(c = getchar()))
    if (c == '-') f = -1;
  do {
    x = (x << 3) + (x << 1) + (c ^ 48);
  } while (isdigit(c = getchar()));
  x *= f;
}
template <class T>
void pt(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) pt(x / 10);
  putchar(x % 10 ^ 48);
}
}  // namespace OI
using namespace OI;
using namespace std;
const int N = 5e5 + 5;
int t, n, k;
long long dp[N][2];
vector<pair<int, int> > G[N];
void dfs(int x, int fa) {
  vector<long long> tp;
  dp[x][0] = dp[x][1] = 0;
  for (auto v : G[x])
    if (v.first != fa) {
      dfs(v.first, x);
      dp[x][0] += dp[v.first][0];
      dp[x][1] += dp[v.first][0];
      tp.push_back(1ll * dp[v.first][1] + v.second - dp[v.first][0]);
    }
  sort(tp.begin(), tp.end(), greater<int>());
  for (int i = 0; i < k && i < (int)tp.size(); i++) {
    if (tp[i] <= 0) break;
    if (i < k - 1) dp[x][1] += tp[i];
    dp[x][0] += tp[i];
  }
}
int main() {
  rd(t);
  while (t--) {
    rd(n), rd(k);
    for (int i = 1, x, y, z; i < n; i++)
      rd(x), rd(y), rd(z), G[x].push_back({y, z}), G[y].push_back({x, z});
    dfs(1, 0);
    pt(dp[1][0]), puts("");
    for (int i = 1; i <= n; i++) G[i].clear();
  }
  return 0;
}
