#include <bits/stdc++.h>
using namespace std;
vector<pair<long long, long long>> v[500001];
long long dp[500001][2];
long long n, k;
void dfs(long long node, long long par) {
  for (auto c : v[node]) {
    if (c.first != par) {
      dfs(c.first, node);
    }
  }
  vector<vector<long long>> check;
  for (auto c : v[node]) {
    if (c.first != par)
      check.push_back({dp[c.first][1] + c.second - dp[c.first][0],
                       dp[c.first][1] + c.second, dp[c.first][0]});
  }
  sort(check.begin(), check.end(), greater<vector<long long>>());
  if (!check.empty()) {
    for (long long i = 1; i < (long long)check.size(); i++) {
      check[i][1] += check[i - 1][1];
    }
    for (long long i = (long long)check.size() - 2; i >= 0; i--) {
      check[i][2] += check[i + 1][2];
    }
  }
  if (!check.empty()) {
    dp[node][0] = max(dp[node][0], check[0][2]);
    dp[node][1] = max(dp[node][1], check[0][2]);
  }
  for (long long i = 0; i < min(k, (long long)check.size()); i++) {
    long long left = 0, right = 0;
    left = check[i][1];
    if (i + 1 < check.size()) right = check[i + 1][2];
    dp[node][0] = max(dp[node][0], left + right);
  }
  for (long long i = 0; i < min(k - 1, (long long)check.size()); i++) {
    long long left = 0, right = 0;
    left = check[i][1];
    if (i + 1 < check.size()) right = check[i + 1][2];
    dp[node][1] = max(dp[node][1], left + right);
  }
}
void solve() {
  cin >> n >> k;
  for (long long i = 0; i < n; i++) {
    v[i].clear();
    dp[i][0] = dp[i][1] = 0;
  }
  for (long long i = 0; i < n - 1; i++) {
    long long a, b, c;
    cin >> a >> b >> c;
    --a;
    --b;
    v[a].emplace_back(b, c);
    v[b].emplace_back(a, c);
  }
  dfs(0, -1);
  cout << max(dp[0][0], dp[0][1]) << endl;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  long long t;
  cin >> t;
  while (t--) solve();
}
