#include <bits/stdc++.h>
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
vector<ii> edge[500005];
int parent[500005];
i64 maxval[500005][2];
int n, k;
void sel(int root, int idx, int ki) {
  priority_queue<int> q;
  for (auto& e : edge[root]) {
    if (e.first == parent[root]) continue;
    maxval[root][idx] += maxval[e.first][0];
    q.push(maxval[e.first][1] + e.second - maxval[e.first][0]);
  }
  while (!q.empty() && ki > 0) {
    auto now = q.top();
    q.pop();
    if (now < 0) break;
    maxval[root][idx] += now;
    ki--;
  }
}
void dfs(int root) {
  for (auto& e : edge[root]) {
    if (e.first == parent[root]) continue;
    parent[e.first] = root;
    dfs(e.first);
  }
  sel(root, 0, k);
  sel(root, 1, k - 1);
}
void solve() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++) {
    edge[i].clear();
    maxval[i][0] = maxval[i][1] = 0;
    parent[i] = 0;
  }
  for (int i = 0; i < n - 1; i++) {
    int x, y, w;
    scanf("%d %d %d", &x, &y, &w);
    edge[x].emplace_back(y, w);
    edge[y].emplace_back(x, w);
  }
  dfs(1);
  printf("%lld\n", maxval[1][0]);
}
int main() {
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) solve();
  return 0;
}
