#include <bits/stdc++.h>
using namespace std;
struct ed {
  int to;
  int w;
  int prev;
};
int n, k;
vector<ed> e;
int last[500500];
void addEdge(int from, int to, int w) {
  e.push_back({to, w, last[from]});
  last[from] = e.size() - 1;
  return;
}
pair<long long, int> answer(int v, int prev) {
  long long ans = 0;
  vector<int> gains;
  for (int i = last[v]; i != -1; i = e[i].prev) {
    if (e[i].to == prev) continue;
    auto x = answer(e[i].to, v);
    ans += x.first;
    if (e[i].w > x.second) gains.push_back(e[i].w - x.second);
  }
  sort(gains.begin(), gains.end(), greater<int>());
  int ans2 = 0;
  for (int i = 0; i < gains.size() && i < k; ++i) {
    ans += gains[i];
  }
  if (gains.size() >= k) ans2 = gains[k - 1];
  return {ans, ans2};
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    e.clear();
    for (int i = 1; i <= n; ++i) {
      last[i] = -1;
    }
    for (int i = 1; i < n; ++i) {
      int a, b, c;
      cin >> a >> b >> c;
      addEdge(a, b, c);
      addEdge(b, a, c);
    }
    cout << answer(1, -1).first << endl;
  }
  return 0;
}
