#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
const long long mod = 1e9 + 7;
long long dp[MAXN][2];
vector<pair<int, long long>> edges[MAXN];
int indeg[MAXN];
long long dfs(int cur, int par, int take) {
  if (dp[cur][take] != -1) return dp[cur][take];
  vector<pair<long long, long long>> res;
  long long res1, res2;
  for (pair<int, long long> i : edges[cur]) {
    if (i.first == par) continue;
    res1 = dfs(i.first, cur, 0);
    res2 = dfs(i.first, cur, 1) + i.second;
    res.push_back({res2 - res1, res1});
  }
  long long ans = 0;
  sort(res.begin(), res.end());
  reverse(res.begin(), res.end());
  for (int i = 0; i < res.size(); i++) {
    if (i < indeg[cur] - take && res[i].first > 0) {
      ans += res[i].first + res[i].second;
    } else {
      ans += res[i].second;
    }
  }
  return dp[cur][take] = ans;
}
int main() {
  int Q, N, K;
  int a, b;
  long long c;
  scanf("%d", &Q);
  for (int _ = 0; _ < Q; _++) {
    scanf("%d %d", &N, &K);
    for (int i = 0; i < N; i++) {
      indeg[i] = 0;
      edges[i].clear();
    }
    for (int i = 0; i < N - 1; i++) {
      scanf("%d %d %lld", &a, &b, &c);
      a--;
      b--;
      indeg[a]++;
      indeg[b]++;
      edges[a].push_back({b, c});
      edges[b].push_back({a, c});
    }
    for (int i = 0; i < N; i++) {
      indeg[i] = min(indeg[i], K);
    }
    for (int i = 0; i < N; i++) {
      dp[i][0] = dp[i][1] = -1;
    }
    printf("%lld\n", dfs(0, -1, 0));
  }
}
