#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int T, n, k;
int final[N], nex[N * 2], to[N * 2], tot;
int w[N * 2];
long long f[N][2];
void link(int x, int y, int ww) {
  to[++tot] = y, nex[tot] = final[x], final[x] = tot;
  w[tot] = ww;
}
vector<long long> a;
void dfs(int x, int fa) {
  for (int i = final[x]; i; i = nex[i]) {
    int y = to[i];
    if (y != fa) {
      dfs(y, x);
    }
  }
  a.clear();
  f[x][0] = f[x][1] = 0;
  for (int i = final[x]; i; i = nex[i]) {
    int y = to[i];
    if (y != fa) {
      a.push_back(f[y][1] - f[y][0] + w[i]);
      f[x][0] += f[y][0];
    }
  }
  f[x][1] = f[x][0];
  sort(a.begin(), a.end());
  int cnt = 0;
  for (int i = a.size() - 1; ~i; i--) {
    cnt++;
    if (cnt <= k) {
      f[x][0] += ((0) > (a[i]) ? (0) : (a[i]));
    }
    if (cnt < k) {
      f[x][1] += ((0) > (a[i]) ? (0) : (a[i]));
    }
  }
}
int main() {
  for (cin >> T; T; T--) {
    scanf("%d %d", &n, &k);
    tot = 0;
    for (int i = 1; i <= n; i++) final[i] = 0;
    for (int i = 1; i < n; i++) {
      int u, v, c;
      scanf("%d %d %d", &u, &v, &c);
      link(u, v, c), link(v, u, c);
    }
    dfs(1, 0);
    printf("%I64d\n", ((f[1][0]) > (f[1][1]) ? (f[1][0]) : (f[1][1])));
  }
}
