#include <bits/stdc++.h>
using namespace std;
inline char gc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline long long read() {
  long long k = 0, f = 1;
  char ch = getchar();
  while (ch < 48 || ch > 57) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= 48 && ch <= 57) {
    k = (k << 1) + (k << 3) + (ch ^ 48);
    ch = getchar();
  }
  return k * f;
}
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void writeln(long long x) {
  write(x);
  puts("");
}
struct node {
  long long to, next, w;
} e[1000500];
struct sdaw {
  long long wz, v;
  friend bool operator<(const sdaw& a, const sdaw& b) { return a.v > b.v; }
};
long long cnt, n, m;
long long head[500500], lj[500500][2], f[500500][2];
void add(long long u, long long v, long long w) {
  ++cnt;
  e[cnt].to = v;
  e[cnt].next = head[u];
  e[cnt].w = w;
  head[u] = cnt;
}
void dfs(long long u, long long fa) {
  vector<sdaw> ve;
  for (long long i = head[u]; i; i = e[i].next) {
    long long v = e[i].to;
    if (v == fa) continue;
    dfs(v, u);
    ve.push_back(sdaw{v, e[i].w + f[v][1] - f[v][0]});
  }
  sort(ve.begin(), ve.end());
  for (long long i = 0; i < ve.size() && i < m; i++) {
    if (ve[i].v <= 0) break;
    if (i < m - 1) {
      f[u][1] += ve[i].v + f[ve[i].wz][0];
      lj[ve[i].wz][1] = 1;
    }
    f[u][0] += ve[i].v + f[ve[i].wz][0];
    lj[ve[i].wz][0] = 1;
  }
  for (long long i = head[u]; i; i = e[i].next) {
    long long v = e[i].to;
    if (v == fa) continue;
    if (!lj[v][1]) f[u][1] += f[v][0];
    if (!lj[v][0]) f[u][0] += f[v][0];
  }
}
signed main() {
  long long q;
  q = read();
  while (q--) {
    n = read();
    m = read();
    for (long long i = 1; i <= n; i++) {
      head[i] = 0;
      lj[i][0] = lj[i][1] = 0;
      f[i][0] = f[i][1] = 0;
    }
    cnt = 0;
    for (long long i = 1; i < n; i++) {
      long long x, y, z;
      x = read();
      y = read();
      z = read();
      add(x, y, z);
      add(y, x, z);
    }
    dfs(1, 0);
    cout << f[1][0] << endl;
  }
}
