#include <bits/stdc++.h>
using namespace std;
const long long N = 500010;
inline long long read() {
  long long s = 0, w = 1;
  register char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
  return s * w;
}
long long n, K, F[N][2];
long long head[N], maxE;
struct Edge {
  long long nxt, to, rdis;
} e[N << 1];
inline void Add(long long u, long long v, long long w) {
  e[++maxE].nxt = head[u];
  head[u] = maxE;
  e[maxE].to = v;
  e[maxE].rdis = w;
}
void DFS(long long x, long long fa) {
  vector<pair<long long, long long> > P;
  long long son = 0;
  for (register long long i = head[x]; i; i = e[i].nxt) {
    long long v = e[i].to;
    if (v == fa) continue;
    DFS(v, x), son++;
    F[x][0] += F[v][1];
    P.emplace_back(make_pair(F[v][0] - F[v][1] + e[i].rdis, v));
  }
  if (son >= K) {
    sort(P.begin(), P.end());
    long long len = (long long)P.size();
    for (register long long i = len - 1; i > len - K; i--)
      F[x][0] += max(0ll, P[i].first);
    F[x][1] = F[x][0] + max(0ll, P[len - K].first);
  } else {
    for (register long long i = head[x]; i; i = e[i].nxt) {
      long long v = e[i].to;
      if (v == fa) continue;
      F[x][1] += max(F[v][1], F[v][0] + e[i].rdis);
    }
    F[x][0] = F[x][1];
  }
}
signed main() {
  for (register long long T = read(); T; T--) {
    n = read(), K = read(), maxE = 0;
    for (register long long i = 1; i <= n; i++) F[i][0] = F[i][1] = head[i] = 0;
    for (register long long i = 1; i < n; i++) {
      long long u, v, w;
      u = read(), v = read(), w = read();
      Add(u, v, w), Add(v, u, w);
    }
    DFS(1, 0);
    printf("%lld\n", max(F[1][0], F[1][1]));
  }
  return 0;
}
