#include <bits/stdc++.h>
using namespace std;
void debug(vector<int> &v) {
  for (int i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
  }
  cout << endl;
}
template <typename T>
vector<T> read_t() {
  int n;
  cin >> n;
  vector<T> R;
  for (int i = 0; i < n; i++) {
    T a;
    cin >> a;
    R.push_back(a);
  }
  return R;
}
long long gcd(long long a, long long b) {
  if (a < b) return gcd(b, a);
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long sum(vector<long long> &vp, int k) {
  if (k == 0) {
    return 0;
  }
  if (vp.size() <= k) {
    long long R = 0;
    for (int i = 0; i < vp.size(); i++) {
      R += vp[i];
    }
    return R;
  }
  nth_element(vp.begin(), vp.begin() + k - 1, vp.end());
  long long R = 0;
  int n = 0;
  for (int i = 0; i < vp.size(); i++) {
    if (vp[i] <= vp[k - 1]) {
      R += vp[i];
      n++;
    }
  }
  R -= (n - k) * vp[k - 1];
  return R;
}
pair<long long, long long> dfs(int n, int k, int node, int f,
                               vector<vector<int> > &v,
                               vector<vector<long long> > &val) {
  vector<long long> vp;
  long long R = 0;
  for (int i = 0; i < v[node].size(); i++) {
    if (f == v[node][i]) continue;
    pair<long long, long long> r = dfs(n, k, v[node][i], node, v, val);
    R += r.first;
    if (r.second + val[node][i] > r.first) {
      vp.push_back(-(r.second + val[node][i] - r.first));
    }
  }
  long long R1 = R, R2 = R;
  R1 -= sum(vp, k);
  R2 -= sum(vp, k - 1);
  return make_pair(R1, R2);
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int n, k;
    cin >> n >> k;
    vector<vector<int> > v(n);
    vector<vector<long long> > val(n);
    for (int i = 0; i < n - 1; i++) {
      long long a, b, w;
      cin >> a >> b >> w;
      a--;
      b--;
      v[a].push_back(b);
      v[b].push_back(a);
      val[a].push_back(w);
      val[b].push_back(w);
    }
    cout << dfs(n, k, 0, -1, v, val).first << endl;
  }
}
