#include <bits/stdc++.h>
using namespace std;
const int maxn = int(5e5) + 100;
int n, m;
vector<pair<int, int> > out[maxn];
int fa[maxn];
long long f[maxn], g[maxn], a[maxn];
void read() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) out[i].clear();
  for (int i = 1; i < n; ++i) {
    int u, v, d;
    scanf("%d%d%d", &u, &v, &d);
    out[u].push_back(make_pair(v, d));
    out[v].push_back(make_pair(u, d));
  }
}
void dfs(int cur) {
  f[cur] = g[cur] = 0;
  for (auto &to : out[cur])
    if (to.first != fa[cur]) {
      fa[to.first] = cur;
      dfs(to.first);
      f[cur] += f[to.first];
      g[cur] += f[to.first];
    }
  int cnt = 0;
  for (auto &to : out[cur])
    if (to.first != fa[cur]) a[++cnt] = to.second + g[to.first] - f[to.first];
  sort(a + 1, a + 1 + cnt, greater<long long>());
  int fin = min(m - 1, cnt);
  for (int i = 1; i <= fin; ++i)
    g[cur] += max(0LL, a[i]), f[cur] += max(a[i], 0LL);
  if (m <= cnt) f[cur] += max(0LL, a[m]);
}
void solve() {
  dfs(1);
  printf("%lld\n", f[1]);
}
int main() {
  int casesum;
  scanf("%d", &casesum);
  while (casesum--) {
    read();
    solve();
  }
  return 0;
}
