#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 5 * 100002;
int k;
ll dp0[maxn], dp1[maxn];
vector<pair<int, ll>> g[maxn];
struct el {
  ll val;
  int gag;
};
bool operator<(const el& a, const el& b) { return a.val > b.val; }
void Solve(int v, int p) {
  vector<el> a;
  for (auto x : g[v])
    if (x.first != p) {
      Solve(x.first, v);
      a.push_back({dp1[x.first] + x.second - dp0[x.first], x.first});
    }
  sort(a.begin(), a.end());
  int cnt = 0;
  for (el x : a) {
    if (cnt == k || x.val < 0) {
      dp1[v] += dp0[x.gag];
      dp0[v] += dp0[x.gag];
      continue;
    }
    if (x.val >= 0) {
      dp0[v] += x.val + dp0[x.gag];
      if (cnt < k - 1)
        dp1[v] += x.val + dp0[x.gag];
      else
        dp1[v] += dp0[x.gag];
      cnt++;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int q;
  cin >> q;
  while (q--) {
    int n;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
      g[i].clear();
      dp0[i] = dp1[i] = 0;
    }
    for (int i = 1; i < n; i++) {
      int u, v;
      ll w;
      cin >> u >> v >> w;
      g[u].push_back({v, w});
      g[v].push_back({u, w});
    }
    Solve(1, -1);
    cout << max(dp1[1], dp0[1]) << '\n';
  }
}
