#include <bits/stdc++.h>
using namespace std;
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << "\n";
  err(++it, args...);
}
const long long int INF = 1e10;
vector<vector<pair<int, int> > > ad(500003);
long long int dp[2][500003];
int k;
void dfs(int s, int p) {
  int w = 0, i, a, x = ad[s].size();
  for (i = 0; i < x; i++) {
    a = ad[s][i].first;
    if (a != p)
      dfs(a, s);
    else
      w = ad[s][i].second;
  }
  a = (x - (w > 0));
  if (a < k) {
    for (i = 0; i < x; i++) {
      a = ad[s][i].first;
      if (a != p)
        dp[0][s] += max(dp[1][a], dp[0][a]);
      else
        w = ad[s][i].second;
    }
    dp[1][s] = dp[0][s] + w;
    return;
  }
  vector<long long int> temp;
  for (i = 0; i < x; i++) {
    a = ad[s][i].first;
    if (a != p)
      dp[0][s] += dp[0][a], temp.emplace_back(dp[1][a] - dp[0][a]);
    else
      w = ad[s][i].second;
  }
  sort(temp.begin(), temp.end());
  reverse(temp.begin(), temp.end());
  for (i = 0; i < k - 1; i++)
    if (temp[i] > 0) dp[0][s] += temp[i];
  dp[1][s] = dp[0][s] + w;
  if (temp[k - 1] > 0) dp[0][s] += temp[k - 1];
  return;
}
int main() {
  int t, n, i, j, a, b, c, s, m;
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &n, &k);
    for (i = 0; i < n; i++) ad[i].resize(0);
    for (i = 0; i < n - 1; i++) {
      scanf("%d%d%d", &a, &b, &c);
      a--, b--;
      ad[a].emplace_back(b, c);
      ad[b].emplace_back(a, c);
    }
    for (i = 0; i < n; i++) dp[0][i] = 0, dp[1][i] = 0;
    dfs(0, -1);
    cout << dp[0][0] << "\n";
  }
}
