#include <bits/stdc++.h>
using namespace std;
const int maxN = 5e5 + 7;
int n, k;
vector<pair<int, int> > Adj[maxN];
long long F[2][maxN];
void DFS(int u, int fa) {
  F[0][u] = F[1][u] = 0;
  vector<long long> V(0);
  for (auto x : Adj[u]) {
    int w = x.first;
    int v = x.second;
    if (v == fa) continue;
    DFS(v, u);
    F[0][u] += F[0][v];
    F[1][u] += F[0][v];
    V.push_back(F[1][v] + w - F[0][v]);
  }
  sort(V.begin(), V.end(), greater<long long>());
  int m = min(k, (int)V.size());
  for (int i = 0; i < m; ++i) {
    if (V[i] < 0) break;
    F[0][u] += V[i];
    if (i < k - 1) F[1][u] += V[i];
  }
}
int main() {
  int ntest;
  scanf("%d\n", &ntest);
  while (ntest--) {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) Adj[i].clear();
    for (int i = 1; i < n; ++i) {
      int u, v, w;
      scanf("%d%d%d\n", &u, &v, &w);
      Adj[u].push_back({w, v});
      Adj[v].push_back({w, u});
    }
    DFS(1, 0);
    printf("%I64d\n", F[0][1]);
  }
  return 0;
}
