#include <bits/stdc++.h>
using namespace std;
int t, n, k;
vector<pair<int, long long>> g[500005];
long long dp[500005][2];
void dfs(int v, int p) {
  vector<pair<long long, long long>> d;
  for (int i = 0; i < g[v].size(); i++) {
    int to = g[v][i].first;
    long long w = g[v][i].second;
    if (to == p) continue;
    dfs(to, v);
    d.push_back(make_pair(max(dp[to][1] + w, dp[to][0]), dp[to][0]));
  }
  sort(d.begin(), d.end(),
       [](pair<long long, long long> a, pair<long long, long long> b) {
         return a.first - a.second > b.first - b.second;
       });
  for (int i = 0; i < d.size(); i++) {
    if (i < k)
      dp[v][0] += d[i].first;
    else
      dp[v][0] += d[i].second;
    if (i < k - 1)
      dp[v][1] += d[i].first;
    else
      dp[v][1] += d[i].second;
  }
}
int main() {
  cin >> t;
  while (t--) {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
      dp[i][0] = dp[i][1] = 0;
      g[i].clear();
    }
    for (int i = 1; i <= n - 1; i++) {
      int a, b;
      long long w;
      scanf("%d%d%lld", &a, &b, &w);
      g[a].push_back(make_pair(b, w));
      g[b].push_back(make_pair(a, w));
    }
    dfs(1, 0);
    printf("%lld\n", dp[1][0]);
  }
  return 0;
}
