#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 8;
int n, k;
vector<pair<long long, long long> > G[maxn];
pair<long long, long long> dp[maxn];
bool cmp(pair<long long, long long>& A, pair<long long, long long>& B) {
  return A.second > B.second;
  return A.first - A.second < B.first - B.second;
}
void dfs(int u, int p, int val) {
  vector<pair<long long, long long> > ve;
  long long sum(0);
  for (auto v : G[u])
    if (v.first != p) dfs(v.first, u, v.second);
  for (auto v : G[u])
    if (v.first != p) ve.push_back(dp[v.first]);
  sort(ve.begin(), ve.end(), cmp);
  for (auto& p : ve) sum += p.first;
  dp[u].first = sum;
  long long maU(0), maNoU(0);
  sum = 0;
  for (int i = int(1); i <= int(ve.size()); ++i) {
    sum += ve[i - 1].second;
    if (i < k) maU = max(maU, sum);
    if (i <= k) maNoU = max(maNoU, sum);
  }
  maU += val;
  dp[u] = {dp[u].first + maNoU, maU - maNoU};
  return;
}
int main() {
  ios::sync_with_stdio(0);
  int T;
  cin >> T;
  while (T--) {
    cin >> n;
    for (int i = int(1); i <= int(n); ++i) G[i].clear();
    cin >> k;
    for (int i = int(1); i <= int(n - 1); ++i) {
      int f, t, v;
      cin >> f >> t >> v;
      G[f].push_back({t, v});
      G[t].push_back({f, v});
    };
    dfs(1, -1, 0);
    cout << dp[1].first << '\n';
  }
}
