#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 ;     }   }   