#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 20;
int q, n, k;
long long dp[N][2];
vector<pair<int, int> > g[N];
void dfs(int v, int par = -1) {
  long long sum = 0;
  vector<long long> vec;
  for (pair<int, int> ed : g[v]) {
    int u = ed.first, w = ed.second;
    if (u == par) {
      continue;
    }
    dfs(u, v);
    sum += dp[u][0];
    long long add = dp[u][1] + w - dp[u][0];
    if (add > 0) {
      vec.push_back(add);
    }
  }
  dp[v][1] = dp[v][0] = sum;
  sort(vec.begin(), vec.end(), greater<long long>());
  for (int i = 0; i < min((int)vec.size(), k); i++) {
    dp[v][0] += vec[i];
    if (i < k - 1) {
      dp[v][1] += vec[i];
    }
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n + 3; i++) {
      g[i].clear();
      dp[i][1] = dp[i][0] = 0;
    }
    for (int i = 0, u, v, w; i < n - 1; i++) {
      scanf("%d%d%d", &u, &v, &w);
      u--;
      v--;
      g[u].push_back({v, w});
      g[v].push_back({u, w});
    }
    dfs(0);
    printf("%lld\n", dp[0][0]);
  }
}
