#include <algorithm>
#include <iostream>
#include <iomanip>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <map>
#include <set>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,102400000")

int n, K;
long long dp[2001][51];
long long INF = 1000000000000000000LL;
vector <int> e[2001];
vector <long long> len[2001];

void dfs(int cur, int from)
{

    long long x[51], t[51];
    for(int i = 0; i <= K; i++)
        x[i] = INF;
    x[0] = 0;
    for(int i = 0; i < e[cur].size(); i++)
    {
        int node = e[cur][i];
        if(node == from) continue;
        dfs(node, cur);
        for(int j = 0; j <= K; j++)
        {
            t[j] = INF;
            for(int k = 0; k <= j; k++)
            {
                long long cost = len[cur][i] * (k) * (K-k);
                t[j] = min(t[j], cost + dp[node][k] + x[j-k]);
            }
        }
        for(int j = 0; j <= K; j++)
            x[j] = t[j];
    }
    for(int i = K; i >= 1; i--)
        x[i] = x[i-1];
    x[0] = 0;
    
    for(int i = 0; i <= K; i++)
        dp[cur][i] = x[i];
    
}

int MAIN()
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n >> K;
        for(int i = 1; i <= n; i++)
        {
            e[i].clear();
            len[i].clear();
        }
        for(int i = 1; i < n; i++)
        {
            int a, b, c;
            cin >> a >> b >> c;
            e[a].push_back(b);
            len[a].push_back(c);
            e[b].push_back(a);
            len[b].push_back(c);
        }
        dfs(1, -1);
        long long ans = INF;
        for(int i = 1; i <= n; i++)
            ans = min(ans, dp[i][K]);
        cout << ans * 2 << endl;
    }
    return 0;
}

int main()
{
    #ifdef LOCAL_TEST
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    ios :: sync_with_stdio(false);
    cout << fixed << setprecision(16);
    return MAIN();
}