#include <bits/stdc++.h>
using namespace std;
ifstream in("boysgirls.in");
ofstream out("boysgirls.out");
struct Edge {
  int to, w;
};
long long dp[511111][2];
int n, k;
struct E {
  long long a, b, c;
};
bool cmp(const E& a, const E& b) {
  if (a.a != b.a) return a.a > b.a;
  if (a.b != b.b) return a.b > b.b;
  return a.c > b.c;
}
void dfs(int v, int p, const vector<vector<Edge> >& g) {
  vector<E> dps;
  long long ans = 0;
  for (const auto& i : g[v]) {
    if (i.to == p) continue;
    dfs(i.to, v, g);
    dps.push_back(
        {dp[i.to][0] - dp[i.to][1] + i.w, dp[i.to][0] + i.w, dp[i.to][1]});
  }
  dp[v][0] = 0;
  dp[v][1] = 0;
  if (g[v].size() == 1 && g[v][0].to == p) return;
  sort(dps.begin(), dps.end(), cmp);
  for (int i = 0; i < min(k - 1, int(dps.size())); ++i)
    ans += (dps[i].a >= 0 ? dps[i].b : dps[i].c);
  for (int i = k; i < dps.size(); ++i) ans += dps[i].c;
  dp[v][0] = ans + (dps.size() >= k ? dps[k - 1].c : 0);
  dp[v][1] = ans + (dps.size() >= k ? max(dps[k - 1].b, dps[k - 1].c) : 0);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int q;
  cin >> q;
  while (q--) {
    cin >> n >> k;
    vector<vector<Edge> > g(n + 1);
    for (int i = 1; i < n; ++i) {
      int u, v, w;
      cin >> u >> v >> w;
      g[v].push_back({u, w});
      g[u].push_back({v, w});
    }
    dfs(1, 0, g);
    cout << dp[1][1] << endl;
  }
}
