#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long n, k, dp[500005][3];
vector<pair<int, long long> > gr[500005];
void dfs(int x, int p) {
  vector<long long> v;
  long long sum = 0, tk = 0, summ = 0;
  for (int i = 0; i < gr[x].size(); i++) {
    pair<int, long long> pr = gr[x][i];
    int u = pr.first, w = pr.second;
    if (u == p) continue;
    dfs(u, x);
    v.push_back(dp[u][0] + w - dp[u][1]);
    sum += dp[u][1];
  }
  sort(v.begin(), v.end());
  for (int i = v.size() - 1; i >= 0; i--) {
    tk++;
    if (tk <= k) {
      if (v[i] > 0) dp[x][1] += v[i];
    }
    if (tk <= k - 1) {
      if (v[i] > 0) dp[x][0] += v[i];
    }
  }
  dp[x][1] += sum, dp[x][0] += sum;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
      int x, y, z;
      cin >> x >> y >> z;
      gr[x].push_back({y, z});
      gr[y].push_back({x, z});
    }
    dfs(1, 0);
    cout << max(dp[1][1], dp[1][0]) << endl;
    for (int i = 1; i <= n; i++) {
      dp[i][0] = 0, dp[i][1] = 0;
      gr[i].clear();
    }
  }
}
