#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
template <class S, class T>
ostream& operator<<(ostream& os, const pair<S, T>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, const unordered_set<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class S, class T>
ostream& operator<<(ostream& os, const unordered_map<S, T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class S, class T>
ostream& operator<<(ostream& os, const map<S, T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
void dbs(string str, T t) {
  cerr << str << " : " << t << "\n";
}
template <class T, class... S>
void dbs(string str, T t, S... s) {
  long long idx = str.find(',');
  cerr << str.substr(0, idx) << " : " << t << ",";
  dbs(str.substr(idx + 1), s...);
}
template <class T>
void prc(T a, T b) {
  cerr << "[";
  for (T i = a; i != b; ++i) {
    if (i != a) cerr << ", ";
    cerr << *i;
  }
  cerr << "]\n";
}
long long power(long long x, long long y) {
  long long res = 1;
  while (y) {
    if (y & 1) res = (res * x) % 1000000007;
    y = y / 2, x = (x * x) % 1000000007;
  }
  return res % 1000000007;
}
long long dp[500001][2];
vector<vector<pair<long long, long long> > > arr(500001);
long long n, k;
bool cmp(pair<long long, long long> a, pair<long long, long long> b) {
  return ((dp[a.first][1] + a.second - dp[a.first][0]) >
          (dp[b.first][1] + b.second - dp[b.first][0]));
}
void dfs(long long u, long long par) {
  vector<pair<long long, long long> > temp;
  for (auto v : arr[u]) {
    if (v.first != par) {
      dfs(v.first, u);
      temp.push_back(v);
    }
  }
  if ((long long)temp.size() == 0) return;
  sort(temp.begin(), temp.end(), cmp);
  long long ma = 0;
  for (long long i = 0; i < (min((long long)temp.size(), k - 1)); i++) {
    long long v = temp[i].first;
    if (dp[v][1] + temp[i].second - dp[v][0] > 0)
      ma += (dp[v][1] + temp[i].second);
    else
      ma += dp[v][0];
  }
  for (long long i = k - 1; i < (long long)temp.size(); i++)
    ma += dp[temp[i].first][0];
  dp[u][1] = ma;
  ma = 0;
  for (long long i = 0; i < (min((long long)temp.size(), k)); i++) {
    long long v = temp[i].first;
    if (dp[v][1] + temp[i].second - dp[v][0] > 0)
      ma += (dp[v][1] + temp[i].second);
    else
      ma += dp[v][0];
  }
  for (long long i = k; i < (long long)temp.size(); i++)
    ma += dp[temp[i].first][0];
  dp[u][0] = ma;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  while (t--) {
    arr.clear();
    cin >> n >> k;
    arr.resize(n + 1);
    long long i;
    for (i = 0; i < n - 1; i++) {
      long long u, v, w;
      cin >> u >> v >> w;
      arr[u].push_back(make_pair(v, w));
      arr[v].push_back(make_pair(u, w));
    }
    for (i = 0; i <= n; i++) dp[i][0] = 0, dp[i][1] = 0;
    dfs(1, 0);
    cout << max(dp[1][0], dp[1][1]) << "\n";
  }
}
