#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000 + 20;
const int INF = 1000000000;
int k, vis[MAXN];
long long dp[MAXN][2];
struct Edge {
  int v, w;
};
vector<Edge> vec[MAXN];
vector<long long> arr[MAXN];
long long dfs(int u) {
  vis[u] = true;
  long long occupy = 0;
  for (int i = 0; i < vec[u].size(); ++i) {
    int v = vec[u][i].v, w = vec[u][i].w;
    if (vis[v]) continue;
    dfs(v);
    occupy += dp[v][1];
    arr[u].push_back(dp[v][0] + w - dp[v][1]);
  }
  long long add = 0;
  sort(arr[u].begin(), arr[u].end(), greater<long long>());
  for (int i = 0, cnt = k; i < arr[u].size() && cnt > 0; ++i, cnt--) {
    if (cnt == 1) dp[u][0] = occupy + add;
    add += max(arr[u][i], (long long)0);
  }
  if (arr[u].size() < k) dp[u][0] = occupy + add;
  dp[u][1] = occupy + add;
  arr[u].clear();
  return max(dp[u][0], dp[u][1]);
}
int main() {
  int _, n;
  cin >> _;
  while (_--) {
    cin >> n >> k;
    for (int i = 0; i <= n; ++i) vec[i].clear();
    memset(dp, 0, sizeof(long long) * 2 * (n + 1));
    memset(vis, 0, sizeof(int) * (n + 1));
    for (int i = 0; i < n - 1; ++i) {
      int u, v, w;
      scanf("%d%d%d", &u, &v, &w);
      vec[u].push_back(Edge{v, w});
      vec[v].push_back(Edge{u, w});
    }
    cout << dfs(1) << endl;
  }
}
