#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<pair<int, long long> > v[500005];
long long memo[500005][2];
long long rek(int node, bool used, int par) {
  if (node and v[node].size() == 1) return 0;
  if (memo[node][used] != -1) return memo[node][used];
  int m = k - used;
  vector<long long> dif;
  long long sol = 0;
  for (int i = 0; i < v[node].size(); i++) {
    if (v[node][i].first == par) continue;
    long long kor = rek(v[node][i].first, 1, node) + v[node][i].second;
    long long nek = rek(v[node][i].first, 0, node);
    sol += nek;
    dif.push_back(kor - nek);
  }
  sort(dif.rbegin(), dif.rend());
  m = min(m, (int)dif.size());
  for (int i = 0; i < m; i++) {
    if (dif[i] <= 0) break;
    sol += dif[i];
  }
  return memo[node][used] = sol;
}
int main() {
  memset(memo, -1, sizeof memo);
  int q;
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n - 1; i++) {
      int x, y, w;
      scanf("%d%d%d", &x, &y, &w);
      x--;
      y--;
      v[x].push_back(make_pair(y, w));
      v[y].push_back(make_pair(x, w));
    }
    printf("%I64d\n", rek(0, 0, -1));
    for (int i = 0; i < n; i++) {
      v[i].clear();
      memo[i][0] = -1;
      memo[i][1] = -1;
    }
  }
  return 0;
}
