#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int nTest, n, K;
vector<vector<pair<int, int> > > gr;
vector<array<LL, 2> > f;
void dfs(int u, int p) {
  vector<LL> vec;
  for (auto pai : gr[u]) {
    int v = pai.first, w = pai.second;
    if (v == p) continue;
    dfs(v, u);
    f[u][0] += f[v][0];
    f[u][1] += f[v][0];
    if (f[v][1] - f[v][0] + w > 0) vec.emplace_back(f[v][1] - f[v][0] + w);
  }
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());
  for (int i = 0; i < (int)vec.size(); ++i) {
    if (i < K) f[u][0] += vec[i];
    if (i < K - 1) f[u][1] += vec[i];
  }
}
void Main() {
  scanf(" %d %d", &n, &K);
  gr.assign(n + 5, vector<pair<int, int> >());
  f.assign(n + 5, {0, 0});
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    scanf(" %d %d %d", &u, &v, &w);
    gr[u].emplace_back(v, w);
    gr[v].emplace_back(u, w);
  }
  dfs(1, 0);
  printf("%lld\n", max(f[1][0], f[1][1]));
}
int main() {
  scanf(" %d", &nTest);
  while (nTest--) Main();
  return 0;
}
