#include <bits/stdc++.h>
using namespace std;
int n, k;
struct Edge {
  int to, next, w;
} e[500010 * 2];
int c1, head[500010];
inline void add_edge(int u, int v, int w) {
  e[c1].to = v;
  e[c1].w = w;
  e[c1].next = head[u];
  head[u] = c1++;
}
long long f[500010], g[500010];
void dfs(int u, int fa) {
  g[u] = 0;
  int t = k;
  vector<long long> A;
  for (int i = head[u]; ~i; i = e[i].next) {
    int v = e[i].to, w = e[i].w;
    if (v == fa) continue;
    dfs(v, u);
    g[u] += g[v];
    A.push_back(f[v] + w - g[v]);
  }
  sort(A.begin(), A.end(), greater<long long>());
  f[u] = g[u];
  for (auto v : A) {
    if (v < 0 || !t) break;
    g[u] += v;
    --t;
    if (t >= 1) f[u] = g[u];
  }
}
void work() {
  cin >> n >> k;
  fill(head + 1, head + n + 1, -1);
  c1 = 0;
  for (int i = 1; i < n; ++i) {
    int x, y, z;
    cin >> x >> y >> z;
    add_edge(x, y, z);
    add_edge(y, x, z);
  }
  dfs(1, 0);
  cout << max(g[1], f[1]) << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int T;
  cin >> T;
  while (T--) work();
  return 0;
}
