#include <bits/stdc++.h>
using namespace std;
long long x, y, z, n, t, k, f[500005][2];
struct node {
  long long v, w;
  node(long long V, long long W) {
    v = V;
    w = W;
  }
};
vector<node> G[500005];
bool cmp(long long x, long long y) { return x > y; }
inline void dfs(long long x, long long fa) {
  vector<long long> now;
  for (register int i = 0; i < G[x].size(); i++) {
    if (G[x][i].v != fa) {
      dfs(G[x][i].v, x);
      f[x][0] += f[G[x][i].v][0];
      f[x][1] += f[G[x][i].v][0];
      now.push_back(f[G[x][i].v][1] + G[x][i].w - f[G[x][i].v][0]);
    }
  }
  sort(now.begin(), now.end(), cmp);
  for (register int i = 0; i < now.size() && i < k; i++) {
    if (now[i] <= 0) break;
    if (i < k - 1) f[x][1] += now[i];
    f[x][0] += now[i];
  }
}
int main() {
  scanf("%lld", &t);
  for (register int T = 1; T <= t; T++) {
    scanf("%lld%lld", &n, &k);
    for (register int i = 1; i < n; i++) {
      scanf("%lld%lld%lld", &x, &y, &z);
      G[x].push_back(node(y, z));
      G[y].push_back(node(x, z));
    }
    dfs(1, 0);
    printf("%lld\n", f[1][0]);
    for (register int i = 1; i <= n; i++) {
      G[i].clear();
    }
    for (register int i = 1; i <= n; i++) f[i][0] = f[i][1] = 0;
  }
}
