#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T& x) {
  char c;
  bool f = 0;
  while ((c = getchar()) < '0' || '9' < c) f |= (c == '-');
  for (x = (c ^ 48); '0' <= (c = getchar()) && c <= '9';
       x = (x << 1) + (x << 3) + (c ^ 48))
    ;
  if (f) x = -x;
}
template <class T>
inline T read(const T sample) {
  T x = 0;
  char c;
  bool f = 0;
  while ((c = getchar()) < '0' || '9' < c) f |= (c == '-');
  for (x = (c ^ 48); '0' <= (c = getchar()) && c <= '9';
       x = (x << 1) + (x << 3) + (c ^ 48))
    ;
  return f ? -x : x;
}
template <class T>
void fwrit(const T x) {
  if (x < 0) return (void)(putchar('-'), fwrit(-x));
  if (x > 9) fwrit(x / 10);
  putchar(x % 10 ^ 48);
}
template <class T>
inline T Max(const T x, const T y) {
  return x > y ? x : y;
}
template <class T>
inline T Min(const T x, const T y) {
  return x < y ? x : y;
}
template <class T>
inline T fab(const T x) {
  return x > 0 ? x : -x;
}
inline int gcd(const int a, const int b) { return b ? gcd(b, a % b) : a; }
inline void getInv(int inv[], const int lim, const int MOD) {
  inv[0] = inv[1] = 1;
  for (int i = 2; i <= lim; ++i)
    inv[i] = 1ll * inv[MOD % i] * (MOD - MOD / i) % MOD;
}
inline long long mulMod(const long long a, const long long b,
                        const long long mod) {
  return ((a * b - (long long)((long double)a / mod * b + 1e-8) * mod) % mod +
          mod) %
         mod;
}
const int MAXN = 5e5;
struct edge {
  int to, nxt;
  long long d;
} e[MAXN * 2 + 5];
int tail[MAXN + 5], ecnt;
inline void add_edge(const int u, const int v, const long long d) {
  e[++ecnt] = edge{v, tail[u], d};
  tail[u] = ecnt;
  e[++ecnt] = edge{u, tail[v], d};
  tail[v] = ecnt;
}
int n, k;
long long f[MAXN + 5][2];
bool used[MAXN + 5];
typedef struct Node_Using_on_Sort {
  int i;
  long long w;
  bool operator<(const Node_Using_on_Sort rhs) const { return w > rhs.w; }
} JZMorz;
void Dfs(const int u, const int fa) {
  static JZMorz Q[MAXN + 5];
  static int sz;
  bool isleaf = true;
  for (signed i = tail[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
    if (v ^ fa) {
      isleaf = false;
      Dfs(v, u);
    }
  if (isleaf) return;
  sz = 0;
  for (signed i = tail[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
    if (v ^ fa) {
      Q[++sz] = JZMorz{v, f[v][1] + e[i].d - f[v][0]};
    }
  sort(Q + 1, Q + sz + 1);
  for (signed i = (1), i_end_ = (Min(k, sz)); i <= i_end_; ++i) {
    if (Q[i].w <= 0) break;
    f[u][0] += Q[i].w + f[Q[i].i][0];
    used[Q[i].i] = true;
    if (i < k) f[u][1] += Q[i].w + f[Q[i].i][0];
  }
  if (k <= sz && used[Q[k].i]) f[u][1] += f[Q[k].i][0];
  for (signed i = tail[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
    if (!used[v] && v != fa) {
      f[u][0] += f[v][0];
      f[u][1] += f[v][0];
    }
}
inline void solve() {
  n = read(1), k = read(1);
  ecnt = 0;
  for (signed i = (0), i_end_ = (n); i <= i_end_; ++i)
    f[i][0] = f[i][1] = tail[i] = used[i] = 0;
  int x, y;
  long long z;
  for (signed i = (1), i_end_ = (n - 1); i <= i_end_; ++i) {
    x = read(1), y = read(1), z = read(1ll);
    add_edge(x, y, z);
  }
  Dfs(1, 0);
  fwrit(f[1][0]), putchar('\n');
}
signed main() {
  for (signed i = (1), i_end_ = (read(1)); i <= i_end_; ++i) solve();
  return 0;
}
