// eddy1021
//#include <bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
typedef double D;
typedef long long ll;
typedef pair<int,int> PII;
#define mod9 1000000009ll
#define mod7 1000000007ll 
#define INF 1023456789ll
#define LLINF (1ll<<62)
#define FI first
#define SE second
#define PB push_back
#define MP make_pair
#define eps 1e-7
ll getint(){
    ll _x=0,_tmp=1; char _tc=getchar();
    while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
    if( _tc == '-' ) _tc=getchar() , _tmp = -1;
    while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
    return _x*_tmp;
}
ll mypow( ll _a , ll _x , ll _mod ){
    if( _x == 0 ) return 1ll;
    ll _tmp = mypow( _a , _x / 2 , _mod );
    _tmp = ( _tmp * _tmp ) % _mod;
    if( _x & 1 ) _tmp = ( _tmp * _a ) % _mod;
    return _tmp;
}
bool equal( D _x ,  D _y ){
    return _x > _y - eps && _x < _y + eps;
}
int __ = 1 , cs;
/*********default*********/
#define N 2010
#define K 51
int n , k;
ll dp[ N ][ K ] , dp2[ K ];
vector<PII> v[ N ];
void build(){

}
void init(){
    n = getint(); k = getint();
    for( int i = 1 ; i <= n ; i ++ ) v[ i ].clear();
    for( int i = 1 ; i < n ; i ++ ){
        int a , b , c;
        a = getint(); b = getint(); c = getint();
        v[ a ].PB( MP( b , c ) );
        v[ b ].PB( MP( a , c ) );
    }
}
ll ans;
void DP( int now , int prt ){
    for( int i = 2 ; i <= k ; i ++ ) dp[ now ][ i ] = LLINF;
    dp[ now ][ 0 ] = dp[ now ][ 1 ] = 0;
    for( int i = 0 ; i < (int)v[ now ].size() ; i ++ ){
        int son = v[ now ][ i ].first;
        ll tw = v[ now ][ i ].second;
        if( son != prt ){
            DP( son , now );
            for( int j = 0 ; j <= k ; j ++ ) dp2[ j ] = dp[ now ][ j ];
            for( int j = 2 ; j <= k ; j ++ )
                for( int l = 1 ; l <= j ; l ++ )
                    if( dp[ son ][ l ] != LLINF && dp[ now ][ j - l ] != LLINF ){
                        ll nxt = dp[ son ][ l ] + dp[ now ][ j - l ];
                        nxt += 2ll * (ll)tw * ( (ll)l * (ll)( k - l ) );
                        if( nxt < dp2[ j ] ) dp2[ j ] = nxt;
                    }
            for( int j = 0 ; j <= k ; j ++ ) dp[ now ][ j ] = dp2[ j ];
        }
    }
    ans = min( ans , dp[ now ][ k ] );
}
void solve(){
    ans = LLINF;
    DP( 1 , -1 );
    cout << ans << endl;
}
int main(){
    build();
    __ = getint();
//    while( cin >> n >> m ){
    while( __ -- ){
        init();
        solve();
    }
}