#include <bits/stdc++.h>
const int mod = 1000000007;
const int inf = 1000000009;
const long long INF = 1000000000000000009;
const long long big = 1000000000000000;
const long double eps = 0.0000000001;
using namespace std;
bool cmp(int a, int b) { return a > b; }
int k;
long long int DP[500005][3];
vector<pair<int, int> > P[500005];
vector<long long int> W;
void dfs(int n, int p) {
  for (auto v : P[n])
    if (v.first != p) dfs(v.first, n);
  long long int wynik = 0;
  for (auto v : P[n]) {
    if (v.first != p) {
      wynik += DP[v.first][2];
      W.push_back(DP[v.first][1] + v.second - DP[v.first][2]);
    }
  }
  sort(W.begin(), W.end(), cmp);
  DP[n][1] = wynik, DP[n][2] = wynik;
  for (int i = 0; i < min(k, (int)W.size()); i++) {
    if (W[i] <= 0) break;
    if (i != k - 1) DP[n][1] += W[i];
    DP[n][2] += W[i];
  }
  W.clear();
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie();
  cout.tie();
  int q;
  cin >> q;
  for (int j = 1; j <= q; j++) {
    int n;
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
      int a, b, c;
      cin >> a >> b >> c;
      P[a].push_back(make_pair(b, c));
      P[b].push_back(make_pair(a, c));
    }
    dfs(1, 0);
    cout << max(DP[1][1], DP[1][2]) << "\n";
    for (int i = 1; i <= n; i++) P[i].clear();
  }
  return 0;
}
