#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int N = 500031;
int tests, n, k;
vector<pair<int, int> > g[N];
int used[N];
long long dp[N][2];
void dfs(int v) {
  used[v] = 1;
  long long guaranteed = 0;
  vector<long long> benefits;
  for (int i = 0; i < g[v].size(); i++) {
    int to = g[v][i].first;
    int cost = g[v][i].second;
    if (used[to] == 1) continue;
    dfs(to);
    long long without_edge = max(dp[to][0], dp[to][1]);
    long long with_edge = dp[to][0] + cost;
    guaranteed += without_edge;
    long long benefit_here = with_edge - without_edge;
    if (benefit_here < 0) benefit_here = 0;
    benefits.push_back(benefit_here);
  }
  sort(benefits.begin(), benefits.end());
  reverse(benefits.begin(), benefits.end());
  long long S = 0;
  for (int i = 0; i < k - 1 && i < benefits.size(); i++) {
    S += benefits[i];
  }
  dp[v][0] = guaranteed + S;
  S = 0;
  for (int i = 0; i < k && i < benefits.size(); i++) {
    S += benefits[i];
  }
  dp[v][1] = guaranteed + S;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> tests;
  for (; tests; --tests) {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
      g[i].clear();
      used[i] = 0;
    }
    for (int i = 1; i < n; i++) {
      int a, b, c;
      cin >> a >> b >> c;
      g[a].push_back(make_pair(b, c));
      g[b].push_back(make_pair(a, c));
    }
    dfs(1);
    cout << max(dp[1][0], dp[1][1]) << endl;
  }
  return 0;
}
