#include <bits/stdc++.h>
using namespace std;
const long long inf = (long long)1e18;
const long long mod = (long long)1e9 + 7;
const double eps = (double)1e-9;
const double pi = acos(-1.0);
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};
const int N = 500500;
int q, n, k;
long long dp[N][2];
vector<pair<int, int> > g[N];
void dfs(int v, int pr = -1) {
  vector<pair<long long, pair<long long, long long> > > vec;
  for (auto i : g[v]) {
    int to = i.first;
    if (to == pr) continue;
    int w = i.second;
    dfs(to, v);
    vec.push_back({dp[to][1] + w - dp[to][0], {dp[to][1] + w, dp[to][0]}});
  }
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());
  int lim = (int)vec.size();
  for (int i = 0; i < (int)vec.size(); i++) {
    if (vec[i].first < 0) {
      lim = i;
      break;
    }
  }
  for (int i = 0; i < min({(int)vec.size(), k, lim}); i++)
    dp[v][0] += vec[i].second.first;
  for (int i = min(k, lim); i < (int)vec.size(); i++)
    dp[v][0] += vec[i].second.second;
  for (int i = 0; i < min({(int)vec.size(), k - 1, lim}); i++)
    dp[v][1] += vec[i].second.first;
  for (int i = min(k - 1, lim); i < (int)vec.size(); i++)
    dp[v][1] += vec[i].second.second;
}
int main() {
  scanf("%d", &q);
  while (q--) {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
      dp[i][0] = dp[i][1] = 0;
      g[i].clear();
    }
    for (int i = 1; i < n; i++) {
      int x, y, z;
      scanf("%d %d %d", &x, &y, &z);
      g[x].push_back({y, z});
      g[y].push_back({x, z});
    }
    dfs(1);
    printf("%lld\n", max(dp[1][0], dp[1][1]));
  }
  return 0;
}
