#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
const long long INF = 1e9;
const long long LINF = INF * INF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1 << 19;
int n, k;
vector<pair<long long, long long>> g[N];
long long dp[N][2];
int cmp(pair<long long, long long> x, pair<long long, long long> y) {
  return x.second - x.first > y.second - y.first;
}
long long get(int treba, vector<pair<long long, long long>>& vec) {
  long long ans = 0;
  for (int i = (0); i < (treba); ++i) ans += max(vec[i].first, vec[i].second);
  for (int i = (treba); i < ((int)((vec).size())); ++i) ans += vec[i].first;
  return ans;
}
void dfs(int v, int p) {
  int sz = (int)((g[v]).size());
  if (v) --sz;
  vector<pair<long long, long long>> vec(sz);
  int ptr = 0;
  for (auto i : g[v])
    if (i.first != p) {
      dfs(i.first, v);
      vec[ptr++] = {dp[i.first][0], dp[i.first][1] + i.second};
    }
  sort(vec.begin(), vec.end(), cmp);
  int zara = min((int)((vec).size()), k);
  dp[v][0] = get(zara, vec);
  zara = min((int)((vec).size()), k - 1);
  dp[v][1] = get(zara, vec);
}
void solve() {
  cin >> n >> k;
  for (int i = (0); i < (n); ++i) g[i].clear();
  for (int i = (0); i < (n - 1); ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    --u;
    --v;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  dfs(0, -1);
  cout << dp[0][0] << endl;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  cin >> t;
  while (t--) solve();
  cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
  return 0;
}
