#include <bits/stdc++.h>

using namespace std;

#define int long long
#define mp make_pair
#define pb emplace_back
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl

using pii = pair <int, int>;

const int N = 2e5 + 10;

int read() {
  int x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
  return x * f;
}

int n, k;
vector <pii> e[N];

struct pq {
  priority_queue <int, vector <int>, greater <int>> q;
  int laz;
  void push(int x) { q.push(x - laz); }
  int top() { return q.top() + laz; }
  void pop() { q.pop(); }
  void down(int x) { laz += x; }
  int size() { return q.size(); }
} ;

struct node {
  pq q1, q2, q3;
  void push(int x) {
    q1.push(x);
    if (q1.size() <= k / 2) return;
    q2.push(q1.top()), q1.pop();
    if (q2.size() <= k % 2) return;
    q3.push(q2.top()), q2.pop();
    if (q3.size() <= k / 2) return;
    q3.pop();
  }
  void down(int x) {
    q1.down(x), q3.down(-x);
  }
  int size() {
    return q1.size() + q2.size() + q3.size();
  }
  int calc() {
    int res = 0;
    for (auto q : {q1, q2, q3}) {
      while (q.size() && q.top() > 0) res += q.top(), q.pop();
    }
    return res;
  }
  void print() {
    int res = 0;
    cout << res << ' ';
    auto q = q1;
    while (q.size()) {
      res += q.top(), q.pop();
      cout << res << ' ';
    }
    q = q2;
    while (q.size()) {
      res += q.top(), q.pop();
      cout << res << ' ';
    }
    q = q3;
    while (q.size()) {
      res += q.top(), q.pop();
      cout << res << ' ';
    }
    cout << endl;
  }
} f[N];

void merge(int u, int v) {
  if (f[u].size() < f[v].size()) swap(f[u], f[v]);
  while (f[v].q1.size()) f[u].push(f[v].q1.top()), f[v].q1.pop();
  while (f[v].q2.size()) f[u].push(f[v].q2.top()), f[v].q2.pop();
  while (f[v].q3.size()) f[u].push(f[v].q3.top()), f[v].q3.pop();
}

void dfs(int u, int fa) {
  for (auto [v, w] : e[u]) if (v != fa) {
    dfs(v, u), f[v].down(2 * w), merge(u, v);
  }
  f[u].push(0);
  // pv(u);
  // f[u].print();
}

void solve() {
  n = read(), k = read();
  rep(i, 1, n - 1) {
    int u = read(), v = read(), w = read();
    e[u].pb(mp(v, w)), e[v].pb(mp(u, w));
  }
  dfs(1, 0);
  printf("%lld\n", f[1].calc());
}

signed main() {
  for (int tc = read(); tc; -- tc) solve();
  return 0;
}