#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, k;
pair<long long, long long> dp[N];
bool mark[N];
vector<pair<int, int> > adj[N];
void _clear_all() {
  for (int i = 0; i < n; i++) {
    dp[i].first = 0;
    dp[i].second = 0;
    adj[i].clear();
    mark[i] = false;
  }
}
void read_input() {
  cin >> n >> k;
  _clear_all();
  for (int i = 1; i < n; i++) {
    int v, u, w;
    cin >> v >> u >> w;
    v--, u--;
    adj[v].push_back(make_pair(u, w)), adj[u].push_back(make_pair(v, w));
  }
}
void dfs(int v) {
  mark[v] = true;
  vector<pair<int, int> > ch;
  for (pair<int, int> p : adj[v]) {
    int u = p.first, w = p.second;
    if (!mark[u]) {
      dfs(u);
      dp[v].first += dp[u].second;
      dp[v].second += dp[u].second;
      ch.push_back(p);
    }
  }
  vector<long long> vec;
  for (pair<int, int> p : ch) {
    int u = p.first, w = p.second;
    if (dp[u].first + w > dp[u].second)
      vec.push_back(dp[u].first + w - dp[u].second);
  }
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());
  for (int i = 0; i < k - 1 && i < vec.size(); i++) dp[v].first += vec[i];
  for (int i = 0; i < k && i < vec.size(); i++) dp[v].second += vec[i];
}
void solve() {
  dfs(0);
  cout << max(dp[0].first, dp[0].second) << '\n';
}
int main() {
  ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  cin >> t;
  while (t--) read_input(), solve();
  return 0;
}
