#include <bits/stdc++.h>
using namespace std;
const int N = (int)(5e5 + 1);
int n, k;
vector<pair<int, int> > g[N];
long long dp[N][2];
void dfs(int v, int p = -1) {
  vector<long long> dobav;
  long long ans1 = 0;
  for (int i = 0; i < g[v].size(); ++i) {
    int to = g[v][i].first;
    int w = g[v][i].second;
    if (to == p) continue;
    dfs(to, v);
    ans1 += dp[to][0];
    dobav.push_back(dp[to][1] + w - dp[to][0]);
  }
  sort(dobav.begin(), dobav.end());
  reverse(dobav.begin(), dobav.end());
  int mn = min((int)dobav.size(), k);
  for (int i = 0; i < mn; ++i)
    if (dobav[i] > 0) ans1 += dobav[i];
  dp[v][0] = dp[v][1] = ans1;
  if (k <= dobav.size() && dobav[k - 1] > 0) dp[v][1] -= dobav[k - 1];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int q;
  cin >> q;
  if (q == 1) {
    cin >> n >> k;
    for (int i = 0; i < n - 1; ++i) {
      int u, v, w;
      cin >> u >> v >> w;
      --u, --v;
      g[u].push_back(make_pair(v, w));
      g[v].push_back(make_pair(u, w));
    }
    dfs(0);
    cout << dp[0][0] << '\n';
  } else if (q > 1) {
    while (q--) {
      cin >> n >> k;
      for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
      }
      dfs(0);
      cout << dp[0][0] << '\n';
      for (int i = 0; i <= n; ++i) g[i].clear(), dp[i][0] = 0, dp[i][1] = 0;
    }
  }
}
