#include <bits/stdc++.h>
using namespace std;
const int N = 510000;
struct Edge {
  int v, next, w;
} edge[N * 2];
int head[N], e;
void erase(int n) {
  memset(head, -1, (n + 1) * 4);
  e = 0;
}
void increase(int u, int v, int w) {
  edge[e].v = v;
  edge[e].next = head[u];
  edge[e].w = w;
  head[u] = e++;
}
int K;
long long ok[N], no[N];
void dfs(int u, int fa) {
  ok[u] = no[u] = 0;
  priority_queue<long long, vector<long long>, greater<long long> > q;
  while (!q.empty()) q.pop();
  for (int t = head[u]; t != -1; t = edge[t].next) {
    int v = edge[t].v;
    if (v == fa) continue;
    int w = edge[t].w;
    dfs(v, u);
    long long d = ok[v] + w - no[v];
    if (d > 0) {
      if (q.size() == K) {
        if (q.top() < d) {
          q.pop();
          q.push(d);
        }
      } else
        q.push(d);
    }
    ok[u] += no[v];
  }
  if (q.size() == K) {
    long long tmp = q.top();
    q.pop();
    while (!q.empty()) {
      ok[u] += q.top();
      q.pop();
    }
    no[u] = ok[u] + tmp;
  } else {
    while (!q.empty()) {
      ok[u] += q.top();
      q.pop();
    }
    no[u] = ok[u];
  }
}
int main() {
  int T;
  cin >> T;
  while (T--) {
    int n, i, j;
    cin >> n >> K;
    int u, v, w;
    erase(n);
    for (i = 0; i < n - 1; i++) {
      scanf("%d%d%d", &u, &v, &w);
      increase(u, v, w);
      increase(v, u, w);
    }
    dfs(1, 1);
    cout << max(ok[1], no[1]) << endl;
  }
  return 0;
}
