#include <bits/stdc++.h>
using namespace std;
int n, k;
int t;
vector<pair<int, int>> adj[500005];
long long int dp[2][500005];
vector<pair<long long int, pair<int, int>>> tmp;
multiset<long long int> s;
void dfs(int i, int p) {
  for (auto j : adj[i])
    if (j.first != p) dfs(j.first, i);
  tmp.clear();
  s.clear();
  for (auto j : adj[i]) {
    if (j.first != p) {
      if (dp[0][j.first] > dp[1][j.first] + j.second)
        tmp.push_back({dp[0][j.first], {j.first, 0}});
      else
        tmp.push_back({dp[1][j.first] + j.second, {j.first, 1}});
    }
  }
  sort(tmp.begin(), tmp.end());
  reverse(tmp.begin(), tmp.end());
  dp[0][i] = dp[1][i] = 0;
  int lim = k;
  for (auto j : tmp) {
    if (lim == 0) {
      if (j.second.second == 1 && s.size()) {
        if (j.first + (*s.rbegin()) > dp[0][j.second.first]) {
          dp[0][i] += j.first + (*s.rbegin());
          s.erase(s.find((*s.rbegin())));
          s.insert(dp[0][j.second.first] - j.first);
        } else
          dp[0][i] += dp[0][j.second.first];
      } else
        dp[0][i] += dp[0][j.second.first];
    } else {
      dp[0][i] += j.first;
      lim -= j.second.second;
      if (j.second.second) s.insert(dp[0][j.second.first] - j.first);
    }
  }
  s.clear();
  lim = k - 1;
  for (auto j : tmp) {
    if (lim == 0) {
      if (j.second.second == 1 && s.size()) {
        if (j.first + (*s.rbegin()) > dp[0][j.second.first]) {
          dp[1][i] += j.first + (*s.rbegin());
          s.erase(s.find((*s.rbegin())));
          s.insert(dp[0][j.second.first] - j.first);
        } else
          dp[1][i] += dp[0][j.second.first];
      } else
        dp[1][i] += dp[0][j.second.first];
    } else {
      dp[1][i] += j.first;
      lim -= j.second.second;
      if (j.second.second) s.insert(dp[0][j.second.first] - j.first);
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> t;
  while (t--) {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) adj[i].clear();
    for (int i = 2; i <= n; i++) {
      int x, y, d;
      cin >> x >> y >> d;
      adj[x].push_back({y, d});
      adj[y].push_back({x, d});
    }
    dfs(1, 1);
    cout << max(dp[0][1], dp[1][1]) << '\n';
  }
  return 0;
}
