#include <stdio.h>
#include <algorithm>

using namespace std;

struct node {
	long long v , a , b;
	node *next;
} pool[41000] , *g[21000];
long long top;
long long n , k;
long long dp[21000][22];
long long lim;
void clear () {
	long long i;
	for ( i = 1 ; i <= top ; i++ ) pool[i] = pool[0];
	for ( i = 1 ; i <= n ; i++ ) {
		g[i] = NULL;
	}
	top = 0;
}
void add ( long long u , long long v , long long a , long long b ) {
	node *tmp = &pool[++top];
	tmp -> v = v; tmp -> a = a; tmp -> b = b; tmp -> next = g[u]; g[u] = tmp;
}
void merge ( long long *now , long long *child ) {
	long long i , j;
	static long long tmp[22];
	for ( i = 0 ; i <= k ; i++ ) tmp[i] = -1;
	for ( i = 0 ; i <= k ; i++ ) {
		for ( j = 0 ; i + j <= k ; j++ ) {
			if ( now[i] != -1 && child[j] != -1 ) {
				if ( now[i] + child[j] <= lim ) {
					if ( tmp[i+j] == -1 ) tmp[i+j] = max ( now[i] , child[j] );
					else tmp[i+j] = min ( tmp[i+j] , max ( now[i] , child[j] ) );
				}
			}
		}
	}
	for ( i = 0 ; i <= k ; i++ ) {
		now[i] = tmp[i];
	}
}
void dfs ( long long i , long long from , long long a , long long b ) {
	for ( node *j = g[i] ; j ; j = j -> next ) if ( j -> v != from ) {
		dfs ( j -> v , i , j -> a , j -> b );
		merge ( dp[i] , dp[j->v] );
	}
	if ( i != 1 ) {
		for ( long long j = k ; j >= 1 ; j-- ) {
			if ( dp[i][j] == -1 && dp[i][j-1] == -1 ) dp[i][j] = -1;
			else if ( dp[i][j] == -1 ) dp[i][j] = dp[i][j-1] + a;
			else if ( dp[i][j-1] == -1 ) dp[i][j] = dp[i][j] + b;
			else dp[i][j] = min ( dp[i][j] + b , dp[i][j-1] + a );
			if ( dp[i][j] > lim ) dp[i][j] = -1;
		}
		if ( dp[i][0] != -1 ) dp[i][0] = dp[i][0] + b;
		if ( dp[i][0] > lim ) dp[i][0] = -1;
	}
	//printf ( "%lld %lld %lld %lld %lld\n" , i , from , a , b , dp[3][1] );
}
bool check ( long long x ) {
	long long i , j;
	lim = x;
	//printf ( "check %lld\n" , lim );
	for ( i = 1 ; i <= n ; i++ ) {
		for ( j = 0 ; j <= k ; j++ ) {
			dp[i][j] = -1;
		}
		dp[i][0] = 0;
	}
	dfs ( 1 , -1 , -1 , -1 );
	/*for ( i = 1 ; i <= n ; i++ ) {
		for ( j = 0 ; j <= k ; j++ ) {
			printf ( "%lld %lld %lld\n" , i , j , dp[i][j] );
		}
	}*/
	if ( dp[1][k] != -1 ) return true;
	return false;
}
void work () {
	long long i , u , v , a , b;
	long long l , r , mid;
	scanf ( "%lld%lld" , &n , &k );
	for ( i = 1 ; i < n ; i++ ) {
		scanf ( "%lld%lld%lld%lld" , &u , &v , &a , &b );
		add ( u , v , a , b );
		add ( v , u , a , b );
	}
	l = 0; r = 1000000000000000ll;
	while ( l < r - 1 ) {
		mid = (l+r) / 2;
		if ( check ( mid ) == true ) r = mid;
		else l = mid;
	}
	printf ( "%lld\n" , r );
}
int main () {
	int t;
	scanf ( "%d" , &t );
	while ( t-- ) {
		work ();
		clear ();
	}
	return 0;
}