#include <bits/stdc++.h>
using namespace std;
const int MM = 5e5 + 5, MOD = 1e9 + 7;
int T, N, K;
vector<pair<int, int>> adj[MM];
pair<long long, long long> dfs(int u, int pa = 1) {
  pair<long long, long long> ret = {0, 0};
  vector<long long> itm;
  for (pair<int, int> e : adj[u]) {
    int v = e.first, w = e.second;
    if (v == pa) continue;
    pair<long long, long long> x = dfs(v, u);
    ret.first += x.second;
    ret.second += x.second;
    itm.push_back(max(0ll, w - (x.second - x.first)));
  }
  sort(begin(itm), end(itm), greater<long long>());
  for (int i = 0; i < min((int)itm.size(), K); ++i) {
    if (i < K - 1)
      ret.first += itm[i], ret.second += itm[i];
    else
      ret.second += itm[i];
  }
  return ret;
}
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> T;
  while (T--) {
    cin >> N >> K;
    for (int i = 1; i <= N; ++i) adj[i].clear();
    for (int i = 1, u, v, w; i < N; ++i) {
      cin >> u >> v >> w;
      adj[u].emplace_back(v, w);
      adj[v].emplace_back(u, w);
    }
    cout << dfs(1).second << "\n";
  }
}
