#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
struct Edge {
  int to, w;
};
int N, K;
long long dp[MAXN][2];
vector<Edge> G[MAXN];
void dfs(int v, int p) {
  vector<long long> vec;
  for (const Edge &e : G[v]) {
    if (e.to == p) continue;
    dfs(e.to, v);
    vec.push_back(dp[e.to][0] - dp[e.to][1] + e.w);
    dp[v][0] += dp[e.to][1];
    dp[v][1] += dp[e.to][1];
  }
  sort(vec.begin(), vec.end(), greater<long long>());
  for (int i = 0; i < vec.size(); i++) {
    if (i < K && vec[i] > 0) dp[v][1] += vec[i];
    if (i < K - 1 && vec[i] > 0) dp[v][0] += vec[i];
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    cin >> N >> K;
    for (int i = 0; i <= N; i++) {
      G[i].clear();
      dp[i][0] = dp[i][1] = 0;
    }
    for (int i = 0; i < N - 1; i++) {
      int u, v, w;
      cin >> u >> v >> w;
      G[u].push_back({v, w});
      G[v].push_back({u, w});
    }
    dfs(1, 1);
    cout << max(dp[1][0], dp[1][1]) << '\n';
  }
}
