#include <bits/stdc++.h>
using namespace std;
vector<long long> D0, D1;
vector<vector<pair<long long, long long> > > G;
bool comp(pair<long long, long long> a, pair<long long, long long> b) {
  return a.second - a.first > b.second - b.first;
}
void dfs(int x, int k, int p = -1) {
  vector<pair<long long, long long> > F;
  for (auto it : G[x]) {
    int y = it.first;
    if (y == p) continue;
    dfs(y, k, x);
    F.push_back(pair<long long, long long>(D0[y], it.second + D1[y]));
  }
  sort(F.begin(), F.end(), comp);
  for (int i = 0; i < (int)F.size(); ++i) {
    if (i < k - 1 and F[i].second > F[i].first)
      D1[x] += F[i].second;
    else
      D1[x] += F[i].first;
    if (i < k and F[i].second > F[i].first)
      D0[x] += F[i].second;
    else
      D0[x] += F[i].first;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int q;
  cin >> q;
  while (q--) {
    int n, k;
    cin >> n >> k;
    G = vector<vector<pair<long long, long long> > >(n);
    D0 = D1 = vector<long long>(n, 0);
    for (int i = 0; i < n - 1; ++i) {
      int x, y, k;
      cin >> x >> y >> k;
      --x;
      --y;
      G[x].push_back(pair<long long, long long>(y, k));
      G[y].push_back(pair<long long, long long>(x, k));
    }
    dfs(0, k);
    cout << D0[0] << '\n';
  }
}
