#include <bits/stdc++.h>
using namespace std;
pair<long long, long long> dfs(vector<pair<int, int> > e[], int k, int x,
                               int p) {
  vector<long long> a;
  long long s = 0;
  for (pair<int, int> y : e[x]) {
    if (y.second != p) {
      pair<long long, long long> t = dfs(e, k, y.second, x);
      s += t.first;
      a.push_back(t.second + y.first - t.first);
    }
  }
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  pair<long long, long long> ret = {s, s};
  for (int i = 0; i < a.size(); i++) {
    if (i < k && a[i] > 0) {
      ret.first += a[i];
    }
    if (i < k - 1 && a[i] > 0) {
      ret.second += a[i];
    }
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  int q;
  cin >> q;
  while (q--) {
    int n, k;
    cin >> n >> k;
    vector<pair<int, int> > e[n];
    for (int i = 0; i < n - 1; i++) {
      int u, v, w;
      cin >> u >> v >> w;
      u--, v--;
      e[u].push_back({w, v});
      e[v].push_back({w, u});
    }
    cout << dfs(e, k, 0, -1).first << endl;
  }
  return 0;
}
