#include <bits/stdc++.h>
using namespace std;
const int maxn = 500005;
long long f[maxn][2], n, k;
vector<pair<int, int> > g[maxn];
void adde(int u, int v, int w) { g[u].push_back({v, w}); }
void dfs(int u, int fa) {
  vector<long long> d;
  d.clear();
  f[u][0] = f[u][1] = 0;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i].first, w = g[u][i].second;
    if (v == fa) continue;
    dfs(v, u);
    f[u][0] += f[v][1];
    f[u][1] += f[v][1];
    d.push_back(-(w + f[v][0] - f[v][1]));
  }
  sort(d.begin(), d.end());
  for (int i = 0; i < k and i < d.size(); i++) {
    int D = -d[i];
    if (D <= 0) break;
    if (i < k - 1) f[u][0] += D;
    f[u][1] += D;
  }
}
int main() {
  ios::sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) {
    for (int i = 1; i <= n; i++) g[i].clear();
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
      int u, v, w;
      cin >> u >> v >> w;
      adde(u, v, w);
      adde(v, u, w);
    }
    dfs(1, 0);
    cout << max(f[1][1], f[1][0]) << endl;
  }
}
