#include <bits/stdc++.h>
using namespace std;
const long long big = 2e9 + 5;
const long long md = 1e9 + 7;
const long long steps[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
void solve();
int main() {
  ios_base ::sync_with_stdio(0);
  cin.tie();
  cout.tie();
  long long q;
  cin >> q;
  for (; q > 0; q--) {
    solve();
  }
  return 0;
}
long long f[1000000][3];
long long n, k;
vector<pair<long long, long long> > nx[1000000];
vector<long long> all;
void dfs(long long v, long long pr) {
  for (auto i : nx[v]) {
    if (i.first == pr) continue;
    dfs(i.first, v);
  }
  long long res = 0;
  all.clear();
  for (auto i : nx[v]) {
    if (i.first == pr) continue;
    res += f[i.first][0];
    all.push_back(f[i.first][1] + i.second - f[i.first][0]);
  }
  sort(all.begin(), all.end());
  reverse(all.begin(), all.end());
  f[v][1] = res;
  for (long long i = 0; i < k - 1 && i < all.size(); i++) {
    if (all[i] > 0) f[v][1] += all[i];
  }
  f[v][0] = res;
  for (long long i = 0; i < k && i < all.size(); i++) {
    if (all[i] > 0) f[v][0] += all[i];
  }
}
void solve() {
  cin >> n >> k;
  for (long long i = 0; i <= n; i++) {
    nx[i].clear();
  }
  for (long long i = 0; i < n - 1; i++) {
    long long x, y, z;
    cin >> x >> y >> z;
    nx[x].push_back(make_pair(y, z));
    nx[y].push_back(make_pair(x, z));
  }
  for (long long i = 1; i <= n; i++) {
    f[i][0] = 0;
    f[i][1] = 0;
  }
  dfs(1, -1);
  cout << max(f[1][0], f[1][1]) << endl;
}
