#include <bits/stdc++.h>
using namespace std;
const long long maxn = 6e5 + 10;
const long long MAX = 1000;
const long long inf = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
long long n, m;
vector<pair<long long, long long> > a[maxn];
long long f[maxn][2];
void dfs(long long now, long long fa) {
  f[now][0] = f[now][1] = 0;
  priority_queue<long long> q;
  for (auto to : a[now])
    if (to.first != fa) {
      dfs(to.first, now);
      if (f[to.first][1] + to.second - f[to.first][0] > 0)
        q.push(f[to.first][1] + to.second - f[to.first][0]);
      f[now][0] += f[to.first][0];
    }
  long long num = m - 1;
  while (!q.empty() && num != 0) {
    num--;
    f[now][0] += q.top();
    q.pop();
  }
  f[now][1] = f[now][0];
  if (!q.empty()) {
    f[now][0] += q.top();
  }
}
void solve() {
  cin >> n >> m;
  for (long long i = (1); i <= (n); ++i) a[i].clear();
  for (long long i = (1); i <= (n - 1); ++i) {
    long long x, y, z;
    cin >> x >> y >> z;
    a[x].push_back(make_pair(y, z));
    a[y].push_back(make_pair(x, z));
  }
  dfs(1, 0);
  cout << (f[1][0]) << '\n';
}
signed main() {
  std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  long long T;
  cin >> T;
  while (T--) {
    solve();
  }
}
