#include <bits/stdc++.h>
using namespace std;
const long long oo = 1e18;
const int maxn = 5e5 + 5;
int T, n, k;
vector<pair<int, int>> adj[maxn];
long long dp[maxn][2];
void dfs(int u, int p) {
  vector<pair<long long, int>> st;
  for (int i = 0; i < ((int)adj[u].size()); i++) {
    auto v = adj[u][i];
    if (v.first == p) continue;
    dfs(v.first, u);
    long long rem = dp[v.first][0] + v.second - dp[v.first][1];
    st.push_back(make_pair(rem, i));
  }
  sort(st.begin(), st.end());
  reverse(st.begin(), st.end());
  long long tot = 0;
  long long tot1 = 0;
  for (int i = 0; i < ((int)st.size()); i++) {
    auto v = adj[u][st[i].second];
    if (i < k)
      tot += dp[v.first][0] + v.second;
    else
      tot += dp[v.first][1];
    if (i < k - 1 && st[i].first >= 0)
      tot1 += dp[v.first][0] + v.second;
    else
      tot1 += dp[v.first][1];
  }
  if (((int)st.size()) >= k) {
    dp[u][1] = max(tot1, tot);
    dp[u][0] = tot1;
  } else {
    dp[u][1] = tot1;
    dp[u][0] = tot1;
  }
}
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
      adj[i].clear();
    }
    for (int i = 0; i < n - 1; i++) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      x--;
      y--;
      adj[x].push_back(make_pair(y, z));
      adj[y].push_back(make_pair(x, z));
    }
    dfs(0, 0);
    printf("%lld\n", max(dp[0][0], dp[0][1]));
  }
  return 0;
}
