#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
constexpr int DEBUG = 0;
struct WeightedEdge {
  int from, to;
  int64 weight;
  WeightedEdge(int from, int to, int64 weight)
      : from(from), to(to), weight(weight) {}
};
vector<vector<WeightedEdge>> ReadUndirectedWeightedGraph(
    int n, int m, bool is_one_indexed = false) {
  vector<vector<WeightedEdge>> graph(n);
  for (int i = 0; i < m; i++) {
    int v1, v2;
    int64 weight;
    cin >> v1 >> v2 >> weight;
    if (is_one_indexed) {
      v1--;
      v2--;
    }
    graph[v1].push_back(WeightedEdge(v1, v2, weight));
    graph[v2].push_back(WeightedEdge(v2, v1, weight));
  }
  return graph;
}
template <typename T>
vector<vector<T>> Make2DVector(int d1, int d2, T default_value) {
  return vector<vector<T>>(d1, vector<T>(d2, default_value));
}
int64 SolveCase() {
  int n, k;
  cin >> n >> k;
  vector<vector<WeightedEdge>> graph =
      ReadUndirectedWeightedGraph(n, n - 1, true);
  vector<vector<int64>> dp = Make2DVector(n, 2, -1LL);
  function<void(int, int)> dfs_fn = [&](int v, int p) {
    int c_count = 0;
    for (const auto& e : graph[v]) {
      if (e.to == p) continue;
      dfs_fn(e.to, v);
      c_count++;
    }
    if (c_count == 0) {
      dp[v][0] = 0;
      dp[v][1] = 0;
      return;
    }
    int64 base = 0;
    vector<int64> ds;
    for (const auto& e : graph[v]) {
      if (e.to == p) continue;
      base += dp[e.to][0];
      int64 d = dp[e.to][1] + e.weight - dp[e.to][0];
      if (d > 0) ds.push_back(d);
    }
    sort(ds.begin(), ds.end());
    reverse(ds.begin(), ds.end());
    int64 d_sum = 0;
    for (int i = 0; i < k - 1 && i < ds.size(); i++) d_sum += ds[i];
    dp[v][1] = base + d_sum;
    dp[v][0] = base + d_sum;
    if (ds.size() >= k) dp[v][0] += ds[k - 1];
    if (DEBUG) {
      cout << "v: " << v << endl;
      cout << dp[v][0] << endl;
      cout << dp[v][1] << endl;
    }
  };
  dfs_fn(0, -1);
  return dp[0][0];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int num_queries;
  cin >> num_queries;
  for (int i = 0; i < num_queries; i++) {
    cout << SolveCase() << endl;
  }
}
