func_code_string: #include <bits/stdc++.h>   using namespace std;   const double PI = acos(-1.0);   const long long INF = 1e9;   const long long LINF = INF * INF;   mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());   const int N = 1 << 19;   int n, k;   vector<pair<long long, long long>> g[N];   long long dp[N][2];   int cmp(pair<long long, long long> x, pair<long long, long long> y) {     return x.second - x.first > y.second - y.first;   }   long long get(int treba, vector<pair<long long, long long>>& vec) {     long long ans = 0;     for (int i = (0); i < (treba); ++i) ans += max(vec[i].first, vec[i].second);     for (int i = (treba); i < ((int)((vec).size())); ++i) ans += vec[i].first;     return ans;   }   void dfs(int v, int p) {     int sz = (int)((g[v]).size());     if (v) --sz;     vector<pair<long long, long long>> vec(sz);     int ptr = 0;     for (auto i : g[v])       if (i.first != p) {         dfs(i.first, v);         vec[ptr++] = {dp[i.first][0], dp[i.first][1] + i.second};       }     sort(vec.begin(), vec.end(), cmp);     int zara = min((int)((vec).size()), k);     dp[v][0] = get(zara, vec);     zara = min((int)((vec).size()), k - 1);     dp[v][1] = get(zara, vec);   }   void solve() {     cin >> n >> k;     for (int i = (0); i < (n); ++i) g[i].clear();     for (int i = (0); i < (n - 1); ++i) {       int u, v, w;       cin >> u >> v >> w;       --u;       --v;       g[u].push_back({v, w});       g[v].push_back({u, w});     }     dfs(0, -1);     cout << dp[0][0] << endl;   }   int main() {     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);     int t;     cin >> t;     while (t--) solve();     cerr <<  Time elapsed:   << clock() / (double)CLOCKS_PER_SEC << endl;     return 0;   }   