#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long nm = 0;
  bool fh = true;
  char cw = getchar();
  for (; !isdigit(cw); cw = getchar()) fh ^= (cw == '-');
  for (; isdigit(cw); cw = getchar()) nm = nm * 10 + (cw - '0');
  return fh ? nm : -nm;
}
int to[500200 << 1], len[500200 << 1], nt[500200 << 1], fs[500200], tot;
int n, K;
pair<long long, long long> sta[500200];
long long F[500200][2];
inline bool cmp(pair<long long, long long> a, pair<long long, long long> b) {
  return a.second - a.first > b.second - b.first;
}
inline void link(int x, int y, int z) {
  to[++tot] = y, len[tot] = z, nt[tot] = fs[x], fs[x] = tot;
}
inline void DP(int x, int val = 0, int last = 0) {
  for (int i = fs[x]; i; i = nt[i])
    if (to[i] ^ last) DP(to[i], len[i], x);
  int top = 0, rem;
  long long all = 0ll;
  for (int i = fs[x]; i; i = nt[i])
    if (to[i] ^ last)
      sta[++top] = make_pair(F[to[i]][0], F[to[i]][1]), all += F[to[i]][0];
  sort(sta + 1, sta + top + 1, cmp), F[x][0] = all, rem = min(K, top);
  for (int i = 1; i <= rem; i++)
    F[x][0] += max(sta[i].second - sta[i].first, 0ll);
  F[x][1] = all + (long long)val, rem = min(K - 1, top);
  for (int i = 1; i <= rem; i++)
    F[x][1] += max(sta[i].second - sta[i].first, 0ll);
}
inline void solve() {
  n = read(), K = read(), memset(fs, tot = 0, sizeof(int) * (n + 1));
  for (int i = 1, x, y, z; i < n; i++)
    x = read(), y = read(), z = read(), link(x, y, z), link(y, x, z);
  DP(1), printf("%lld\n", max(F[1][0], F[1][1]));
}
int main() {
  for (int Cas = read(); Cas; --Cas) solve();
  return 0;
}
