#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
long long int q, n, k, u, w, v, dp[2][510000];
vector<vector<pair<int, int> > > tree(510000);
void dfs(int index, int par) {
  int numchild = 0;
  for (auto edge : tree[index]) {
    if (edge.first == par) continue;
    numchild++;
    dfs(edge.first, index);
  }
  vector<long long int> v;
  if (numchild >= k) {
    dp[1][index] = 0;
    for (auto edge : tree[index]) {
      if (edge.first == par) continue;
      dp[1][index] += (dp[1][edge.first] + edge.second);
      v.push_back(dp[0][edge.first] - (dp[1][edge.first] + edge.second));
    }
    dp[0][index] = dp[1][index];
    sort(v.begin(), v.end());
    int lef = numchild;
    for (int i = v.size() - 1; i >= 0; i--) {
      if (v[i] < 0 and lef < k) break;
      dp[1][index] += v[i];
      if (lef > k or v[i] > 0) dp[0][index] += v[i];
      lef--;
    }
  } else {
    for (auto edge : tree[index]) {
      if (edge.first == par) continue;
      dp[1][index] += max(edge.second + dp[1][edge.first], dp[0][edge.first]);
    }
    dp[0][index] = dp[1][index];
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> q;
  while (q--) {
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
      cin >> u >> v >> w;
      tree[u].push_back(make_pair(v, w));
      tree[v].push_back(make_pair(u, w));
    }
    dfs(1, -1);
    cout << max(dp[1][1], dp[0][1]) << "\n";
    for (int i = 1; i <= n; i++) {
      tree[i].clear();
      dp[0][i] = dp[1][i] = 0;
    }
  }
}
