#include <bits/stdc++.h>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ') {
  while (!isdigit(ch = getchar()))
    if (ch == '-') f = -1;
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return f * x;
}
const int N = 5e5 + 5;
struct Edge {
  int next, to, w;
  Edge(int next = 0, int to = 0, int w = 0) : next(next), to(to), w(w){};
} edge[N << 1];
int tot, head[N];
void _add(int x, int y, int z) {
  edge[++tot] = Edge(head[x], y, z), head[x] = tot;
}
void add(int x, int y, int z) { _add(x, y, z), _add(y, x, z); }
int q, n, k;
long long f[N], g[N];
void dfs(int x, int fa) {
  f[x] = g[x] = 0;
  vector<long long> s;
  for (int i = head[x]; i; i = edge[i].next) {
    int y = edge[i].to, z = edge[i].w;
    if (y == fa) continue;
    dfs(y, x), f[x] = g[x] += max(g[y], f[y]),
               s.push_back(max(f[y], g[y]) - g[y] - z);
  }
  sort(s.begin(), s.end());
  for (int i = 0; i < s.size() && i < k; ++i)
    if (s[i] < 0)
      f[x] -= s[i];
    else
      break;
  for (int i = 0; i < s.size() && i < k - 1; ++i)
    if (s[i] < 0)
      g[x] -= s[i];
    else
      break;
}
int main() {
  q = read();
  while (q--) {
    n = read(), k = read(), tot = 0, memset(head + 1, 0, sizeof(int) * n);
    for (int i = 1; i < n; ++i) {
      int x = read(), y = read(), z = read();
      add(x, y, z);
    }
    dfs(1, 0), printf("%I64d\n", max(f[1], g[1]));
  }
  return 0;
}
