#include <bits/stdc++.h>
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e5 + 10;
int q, n, k;
int u, v, w;
vector<int> V[N], G[N];
long long dp[N][2];
void solve(int cur, int fa) {
  priority_queue<int> Q;
  dp[cur][1] = dp[cur][0] = 0;
  for (int i = 0; i < (int)V[cur].size(); i++) {
    int u = V[cur][i];
    int w = G[cur][i];
    if (u == fa) continue;
    solve(u, cur);
    dp[cur][0] += dp[u][1];
    Q.push(w - dp[u][1] + dp[u][0]);
  }
  for (int i = 0; i < k - 1 && !Q.empty(); i++) {
    dp[cur][0] = max(dp[cur][0], dp[cur][0] + Q.top());
    Q.pop();
  }
  dp[cur][1] = dp[cur][0];
  if (!Q.empty()) {
    dp[cur][1] = max(dp[cur][1], dp[cur][1] + Q.top());
    Q.pop();
  }
}
int main() {
  scanf("%d", &q);
  while (q--) {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
      V[i].clear();
      G[i].clear();
    }
    for (int i = 1; i <= n - 1; i++) {
      scanf("%d %d %d", &u, &v, &w);
      V[u].push_back(v);
      G[u].push_back(w);
      V[v].push_back(u);
      G[v].push_back(w);
    }
    solve(1, 0);
    cout << max(dp[1][0], dp[1][1]) << endl;
  }
  return 0;
}
