#include <bits/stdc++.h>
using namespace std;
long long INF = (long long)1e20;
long long mod = (long long)1e9 + 7;
pair<long long, long long> solve(
    long long v, vector<vector<pair<long long, long long>>> &nodes, long long p,
    long long k) {
  vector<pair<pair<long long, long long>, long long>> a;
  vector<pair<pair<long long, long long>, long long>> b;
  for (int i = 0; i < nodes[v].size(); ++i) {
    if (nodes[v][i].first != p) {
      pair<long long, long long> kek = solve(nodes[v][i].first, nodes, v, k);
      kek.first += nodes[v][i].second;
      if (kek.second > kek.first) {
        b.push_back({kek, nodes[v][i].second});
      } else {
        a.push_back({kek, nodes[v][i].second});
      }
    }
  }
  vector<pair<pair<long long, long long>, pair<long long, long long>>> vv(
      a.size());
  for (int i = 0; i < a.size(); ++i) {
    vv[i] = {{a[i].first.first - a[i].first.second, a[i].second}, {a[i].first}};
  }
  sort(vv.rbegin(), vv.rend());
  long long sum1 = 0;
  for (int i = 0; i < a.size(); ++i) {
    if (i < k) {
      sum1 += vv[i].second.first;
    } else {
      sum1 += vv[i].second.second;
    }
  }
  for (int i = 0; i < b.size(); ++i) {
    sum1 += b[i].first.second;
  }
  long long sum = 0;
  if (a.size() < k) {
    sum = sum1;
  }
  for (int i = 0; i < a.size(); ++i) {
    if (i < k) {
      long long nw = sum1 - vv[i].second.first;
      nw += vv[i].second.second;
      sum = max(sum, nw);
    } else
      break;
  }
  return {sum, sum1};
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long q;
  cin >> q;
  while (q--) {
    long long n, k;
    cin >> n >> k;
    vector<vector<pair<long long, long long>>> nodes(n);
    for (int i = 0; i < n - 1; ++i) {
      long long u, v, w;
      cin >> u >> v >> w;
      nodes[u - 1].push_back({v - 1, w});
      nodes[v - 1].push_back({u - 1, w});
    }
    pair<long long, long long> ans = solve(0, nodes, 0, k);
    cout << max(ans.first, ans.second) << '\n';
  }
}
