#include <stdio.h>
#include <vector>
#include <iostream>
using namespace std;
#define K 52
#define N 2010
typedef long long ll;
int getint(){
    int x=0,tmp=1; char c=getchar();
    while( (c<'0'||c>'9')&&c!='-' ) c=getchar();
    if( c == '-' ) c=getchar() , tmp = -1;
    while(c>='0'&&c<='9') x*=10,x+=(c-'0'),c=getchar();
    return x*tmp;
}
vector< pair<int,ll> > v[ N ];
int t , n , k;
ll dp[ N ][ K ] , ans;
void init(){
    n = getint(); k = getint(); ans = -1;
    for( int i = 1 ; i <= n ; i ++ ){
        v[ i ].clear();
        for( int j = 2 ; j <= k ; j ++ )
            dp[ i ][ j ] = -1;
        dp[ i ][ 0 ] = dp[ i ][ 1 ] = 0;
    }
    for( int i = 1 ; i < n ; i ++ ){
        int tu , tv , tc;
        tu = getint(); tv = getint(); tc = getint();
        v[ tu ].push_back( make_pair( tv , (ll)tc ) );
        v[ tv ].push_back( make_pair( tu , (ll)tc ) );
    }
}
ll tmp[ K ];
void DP( int now , int p ){
    for( int i = 0 ; i < (int)v[ now ].size() ; i ++ ){
        int son = v[ now ][ i ].first;
        if( son == p ) continue;
        ll cst = v[ now ][ i ].second;
        DP( son , now );
        for( int j = 0 ; j <= k ; j ++ )
            tmp[ j ] = dp[ now ][ j ];
        for( int j = 1 ; j <= k ; j ++ )
            if( dp[ son ][ j ] == -1 ) break;
            else{
                for( int u = k ; u >= j ; u -- )
                    if( dp[ now ][ u - j ] != -1 ){
                        if( tmp[ u ] == -1 || ( dp[ now ][ u - j ] + dp[ son ][ j ] + 2ll * cst * (ll)j * (ll)( k - j ) < tmp[ u ] ) )
                            tmp[ u ] = dp[ now ][ u - j ] + dp[ son ][ j ] + 2ll * cst * (ll)j * (ll)( k - j );
                    }
            }
        for( int j = 0 ; j <= k ; j ++ )
            dp[ now ][ j ] = tmp[ j ];
    }
    if( dp[ now ][ k ] != -1 && ( ans == -1 || dp[ now ][ k ] < ans ) )
        ans = dp[ now ][ k ];
}
void solve(){
    DP( 1 , -1 );
    cout << ans << endl;
}
int main(){
    t = getint(); while( t -- ){
        init();
        solve();
    }
}