#include <bits/stdc++.h>
using namespace std;
inline long long mod(long long n, long long m) {
  long long ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}
long long gcd(long long a, long long b) {
  return (b == 0LL ? a : gcd(b, a % b));
}
long long exp(long long a, long long b, long long m) {
  if (b == 0LL) return 1LL;
  if (b == 1LL) return mod(a, m);
  long long k = mod(exp(a, b / 2, m), m);
  if (b & 1LL) {
    return mod(a * mod(k * k, m), m);
  } else
    return mod(k * k, m);
}
const long long N = 500100;
vector<pair<long long, long long> > g[N];
long long dp[N][2];
long long pai[N];
long long n, k;
long long solve(long long v, long long p) {
  long long &x = dp[v][p];
  if (x != -1) return x;
  x = 0;
  vector<pair<long long, long long> > op;
  for (auto e : g[v]) {
    long long to = e.first;
    if (to == pai[v]) continue;
    pai[to] = v;
    solve(to, 0);
    solve(to, 1);
    op.push_back(
        pair<long long, long long>(solve(to, 0), solve(to, 1) + e.second));
  }
  vector<pair<long long, long long> > idk;
  for (auto it : op) {
    if (it.first >= it.second) {
      x += it.first;
    } else {
      idk.push_back(it);
    }
  }
  sort(idk.begin(), idk.end(),
       [&](pair<long long, long long> a, pair<long long, long long> b) {
         return a.second - a.first > b.second - b.first;
       });
  for (long long i = 0; i < idk.size(); i++) {
    pair<long long, long long> it = idk[i];
    if (i < k - p) {
      x += it.second;
    } else {
      x += it.first;
    }
  }
  return x;
}
void QUERY() {
  cin >> n >> k;
  for (long long i = 1; i <= n; i++) {
    g[i].clear();
    dp[i][0] = dp[i][1] = -1;
  }
  for (long long i = 0; i < n - 1; i++) {
    long long a, b, c;
    cin >> a >> b >> c;
    g[a].push_back(pair<long long, long long>(b, c));
    g[b].push_back(pair<long long, long long>(a, c));
  }
  cout << solve(1, 0) << "\n";
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long t;
  cin >> t;
  while (t--) {
    QUERY();
  }
}
