#include <bits/stdc++.h>
using namespace std;
long long n, k;
struct Node;
vector<Node> tree;
map<int, vector<int>> hs;
struct Node {
  int id;
  int parent;
  vector<pair<int, long long>> adj;
  long long hcost = 0, lcost = 0;
  void treeify(int p, int h) {
    hs[-h].push_back(id);
    for (int i = adj.size() - 1; i >= 0; i--) {
      if (adj[i].first == p) {
        parent = p;
      } else {
        tree[adj[i].first].treeify(id, h + 1);
      }
    }
  }
  void calc(int k) {
    vector<long long> imp;
    long long cost = 0;
    for (auto& child : adj) {
      if (child.first == parent) continue;
      cost += tree[child.first].hcost;
      imp.push_back(tree[child.first].lcost - tree[child.first].hcost +
                    child.second);
    }
    sort(imp.rbegin(), imp.rend());
    for (int i = 0; i < min(k - 1, (int)imp.size()); i++) {
      cost += max(0LL, imp[i]);
    }
    lcost = cost;
    if (k - 1 < imp.size()) cost += max(0LL, imp[k - 1]);
    hcost = cost;
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  int times;
  cin >> times;
  while (times-- > 0) {
    hs.clear();
    cin >> n >> k;
    tree = vector<Node>(n);
    for (int i = 0; i < n; i++) {
      tree[i].id = i;
    }
    for (int i = 0; i < n - 1; i++) {
      int a, b, w;
      cin >> a >> b >> w;
      a--;
      b--;
      tree[a].adj.push_back({b, w});
      tree[b].adj.push_back({a, w});
    }
    tree[0].treeify(-1, 0);
    for (auto& p : hs) {
      for (auto x : p.second) tree[x].calc(k);
    }
    cout << tree[0].hcost << "\n";
  }
  return 0;
}
