#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1000000000;
const ll LINF = 1001002003004005006ll;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}
struct IOSetup {
  IOSetup() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(12);
  }
} iosetup;
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  os << p.first << " " << p.second;
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (int i = 0; i < (int)v.size(); i++)
    os << v[i] << (i + 1 == (int)v.size() ? "" : " ");
  return os;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
  is >> p.first >> p.second;
  return is;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &x : v) is >> x;
  return is;
}
using P = pair<int, ll>;
void solve() {
  int n, k;
  cin >> n >> k;
  vector<vector<P>> g(n);
  for (int i = 0; i < (n - 1); i++) {
    int u, v;
    ll c;
    cin >> u >> v >> c;
    u--, v--;
    g[u].push_back({v, c});
    g[v].push_back({u, c});
  }
  vector<vector<ll>> dp(n, vector<ll>(2, 0));
  function<void(int, int)> dfs = [&](int pre, int now) {
    vector<ll> merit;
    ll ret = 0;
    for (auto [to, c] : g[now])
      if (pre != to) {
        dfs(now, to);
        ret += dp[to][0];
        merit.push_back(dp[to][1] + c - dp[to][0]);
      }
    sort(merit.begin(), merit.end());
    reverse(merit.begin(), merit.end());
    ll dead = ret, alive = ret;
    for (int i = 0; i < (min(k, (int)merit.size())); i++) {
      if (merit[i] > 0) {
        dead += merit[i];
        if (i < k - 1) alive += merit[i];
      }
    }
    dp[now][0] = dead;
    dp[now][1] = alive;
    return;
  };
  dfs(-1, 0);
  cout << max(dp[0][0], dp[0][1]) << endl;
}
signed main() {
  int q;
  cin >> q;
  while (q--) solve();
  return 0;
}
