#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
int n, q, k, p[MAXN];
vector<pair<int, int> > adj[MAXN];
vector<long long> diff[MAXN];
bool built[MAXN];
long long ans[MAXN][2];
bool found[MAXN][2];
void reset() {
  for (int i = 0; i <= n; ++i) {
    adj[i].clear();
    diff[i].clear();
    built[i] = false;
    for (int j = 0; j < 2; ++j) {
      found[i][j] = false;
      ans[i][j] = 0LL;
    }
  }
}
void input() {
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n - 1; ++i) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    adj[u].push_back(pair<int, int>(v, w));
    adj[v].push_back(pair<int, int>(u, w));
  }
}
void dfs(int pos, int prev) {
  p[pos] = prev;
  for (auto i : adj[pos])
    if (i.first != prev) {
      dfs(i.first, pos);
    }
}
long long dp(int pos, bool conned) {
  if (found[pos][conned]) return ans[pos][conned];
  found[pos][conned] = true;
  if (!built[pos]) {
    for (auto i : adj[pos])
      if (i.first != p[pos]) {
        diff[pos].push_back(dp(i.first, true) + i.second - dp(i.first, false));
      }
    sort(diff[pos].begin(), diff[pos].end(),
         [](long long a, long long b) { return a > b; });
    built[pos] = true;
  }
  for (auto i : adj[pos])
    if (i.first != p[pos]) {
      ans[pos][conned] += dp(i.first, false);
    }
  int rem = k - (conned);
  for (int i = 0; i < min((int)diff[pos].size(), rem); ++i) {
    if (diff[pos][i] > 0) ans[pos][conned] += diff[pos][i];
  }
  return ans[pos][conned];
}
void work() {
  dfs(1, -1);
  printf("%lld\n", dp(1, false));
}
int main() {
  scanf("%d", &q);
  while (q--) {
    reset();
    input();
    work();
  }
}
