#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int tc;
long long n, k, dp[N][2];
vector<pair<int, int>> g[N];
void init() {
  for (int i = 1; i <= n; ++i) g[i].clear(), dp[i][0] = dp[i][1] = 0;
}
void dfs(int u, int p) {
  vector<pair<long long, pair<long long, long long>>> v;
  for (auto &c : g[u]) {
    if (c.first != p) {
      dfs(c.first, u);
      v.push_back({dp[c.first][1] - dp[c.first][0] + c.second,
                   {dp[c.first][0], dp[c.first][1]}});
    }
  }
  int cnt = 0;
  sort(v.rbegin(), v.rend());
  for (int i = 0; i < v.size(); ++i) {
    if (cnt < k && v[i].first > 0)
      dp[u][0] += v[i].first + v[i].second.first;
    else
      dp[u][0] += v[i].second.first;
    if (cnt < k - 1 && v[i].first > 0)
      dp[u][1] += v[i].first + v[i].second.first;
    else
      dp[u][1] += v[i].second.first;
    ++cnt;
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> tc;
  while (tc--) {
    cin >> n >> k;
    init();
    for (int i = 1; i < n; ++i) {
      int u, v, w;
      cin >> u >> v >> w;
      g[u].emplace_back(v, w);
      g[v].emplace_back(u, w);
    }
    dfs(1, 0);
    cout << dp[1][0] << '\n';
  }
  return 0;
}
