//[Author]   tuxedcat
//[Date]     2023.03.23
//[File]     src/saved/18755.cpp
//[Library]  https://github.com/tuxedcat/pslib
#pragma GCC optimize("O3")
// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
using namespace std;
#define SYSCALL_ALLOWED 1
#if SYSCALL_ALLOWED
	#include <bits/extc++.h>
	#include <ext/rope>
#endif

#define int i64
using fp=double; //long double,__float128
#define COUT_FP 10
#define FP_EPS 1e-11

#define CPP20 1
#define DBG_SETW 3
#define CHECK_INPUT 1

// Frequently used options
#define endl '\n' // Remove it when interactive
#define TC get<0>(input()) //1
#define TC_OUT_PREFIX ""//"Case #",ti,": "

#define fi first
#define se second
#define mkp make_pair
#define mkt make_tuple
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define itos to_string
#define head(x) (x.begin())
#define tail(x) prev(x.end())
#define dbg(...) void(0)
#define dbgif(...) void(0)
#define dbg1(...) void(0)
#define dbg1if(...) void(0)
using i64=long long;using u64=unsigned long long;using u32=unsigned;
using pint=pair<int,int>;using tint=tuple<int,int,int>;
template<class T>using Str=basic_string<T>;
template<class T,class CMP=less<>>using PQ=std::priority_queue<T,vector<T>,CMP>;

#if CPP20
template<class T>concept Printable=requires(T x){cout<<x<<endl;};
template<class T>concept NotPrintable=not Printable<T>;
template<class T>concept Iterable=requires(T x){x.begin();x.end();begin(x);end(x);};
#else
#define Printable class
#define NotPrintable class
#define Iterable class
#endif
//functions before include <arr.h>

//Math
#if !(CPP20)
	#define countl_zero(x) __builtin_clzll(x)
	#define popcount(x) __builtin_popcountll(x)
	#define bit_ceil(x) (1<<clg2(x))
#endif
#if CPP20
	#define sz ssize
#else
	template<class T>int sz(const T& x){return x.size();}
#endif
int fdiv(int a,int b){if(b<0)a=-a,b=-b;return (a>0)?a/b:(a-b+1)/b;}
int cdiv(int a,int b){if(b<0)a=-a,b=-b;return (a>0)?(a+b-1)/b:a/b;}
i64 flg2(u64 x){return 63-countl_zero(x);}
i64 clg2(u64 x){return x-1==0?0:64-countl_zero(x-1);}
int fsqrt(i64 n) {i64 i=1;while(i*i<=n)i++;return i-1;}
int csqrt(i64 n) {i64 i=1;while(i*i<n)i++;return i;}
template<class T>T sq(T x){return x*x;}
template<class T>constexpr T inf(){return numeric_limits<T>::max()/2;}
template<class T> [[deprecated("use optional")]] constexpr T nan(){return inf<T>()+1;}
#if CPP20
template<typename T> concept MemberInf=requires(T t){t.inf();};
template<typename T> concept MemberNan=requires(T t){t.nan();};
template<MemberInf T>T inf(){return T().inf();}
template<MemberNan T> [[deprecated("use optional")]] T nan(){return T().nan();}
#endif

//IO & misc
template<class...A>void osprint(ostream& os, A...a){((os<<a),...);}
template<class...A>void osprintln(ostream& os, A...a){((os<<a),...,(cout<<endl));}
#define print(...) osprint(cout,__VA_ARGS__)
#define println(...) osprintln(cout,__VA_ARGS__)
#if DEBUG
	#define dbgprint(...) osprint(cerr,"\033[0;33m",__VA_ARGS__,"\033[0m")
	#define dbgprintln(...) osprintln(cerr,"\033[0;33m",__VA_ARGS__,"\033[0m")
#else
	#define dbgprint(...)
	#define dbgprintln(...)
#endif
template<class T,class U>bool assmin(T& a,U&& b){return a>b?a=b,true:false;}
template<class T,class U>bool assmax(T& a,U&& b){return a<b?a=b,true:false;}
void MUST(bool expr){
#if DEBUG
	#include <csignal>
	if(!expr)
		raise(SIGINT);
#endif
}
#define ARG(...) __VA_ARGS__
#define func(RetT,fname,...) function<RetT(__VA_ARGS__)> fname=[&](__VA_ARGS__)->RetT
#define lam(expr,...) [&](__VA_ARGS__){return expr;}
#define lamp(expr,...) [](__VA_ARGS__){return expr;}

auto val2cmp(auto val){return [val](auto x, auto y){return mkp(val(x),x)<mkp(val(y),y);};}

template<class T, class P=vector<T>>
struct Arr:public P{
	Arr(){P::shrink_to_fit();}
	explicit Arr(signed n):P(n){}
	explicit Arr(signed n,T init):P(n,init){}
	Arr(initializer_list<T>il):P(il){}
	Arr(auto its, auto ite):P(its,ite){}
	inline T& operator[](signed i){
		int n=sz(*this);
		if(i<0)
			i+=n,dbg1("Neg Index Found");
		if(i>=n)
			i-=n,dbg1("Over Index Found");
		return P::operator[](i);
	}
	const T& operator[](signed i)const{	
		int n=sz(*this);
		if(i<0)
			i+=n,dbg1("Neg Index Found");
		if(i>=n)
			i-=n,dbg1("Over Index Found");
		return P::operator[](i);
	}
	T& at(signed i){return *this[i];}
	const T& at(signed i)const{return *this[i];}
};
template<class... A> auto ARR(auto n,A&&... a)
{if constexpr(!sizeof...(a)) return n; else return Arr(n,ARR(a...));}

//Consts
// const fp pi=numbers::pi_v<fp>,eps=FP_EPS;
const fp pi=acos(-1),eps=FP_EPS;
const int dir4[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
const int dir8[8][2]={{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}};
//functions after include <arr.h>

template<class T>int argmin(const Arr<T>& a){return min_element(a.begin(),a.end())-a.begin();}
template<class T>int argmax(const Arr<T>& a){return max_element(a.begin(),a.end())-a.begin();}
Arr<int> permuinv(const Arr<int>& a){Arr<int> r(sz(a));for(int i=0;i<sz(a);i++)r[a[i]]=i;return r;}
template<class T,class U=Arr<int>>map<T,U> classify(const Arr<T>& a){
	map<T,U> r;
	for(int i=0;i<sz(a);i++)
		r[a[i]].push_back(i);
	return r;
}
#if CPP20

template<class T=int,class... Ts> requires (!Iterable<T>) tuple<T,Ts...> input(){
	T x; cin>>x;
	if constexpr (sizeof...(Ts)==0) return mkt(x);
	else return tuple_cat(mkt(x),input<Ts...>());
}
template<class T=int,int n>std::array<T,n> input(){
	std::array<T,n> a;
	for(auto&i:a)
		i=get<0>(input<T>());
	return a;
}
string input(string& str){ cin>>str; return str; }
template<class T> requires (!Iterable<T>) T& input(T& a){ cin>>a; return a;}
template<class T> requires Iterable<T> T& input(T& a){ for(auto&i:a)input(i); return a; }
#else
	#define input() [](){int x;cin>>x;return mkt(x);}()
	// #define input(n) [](){Arr<int> a(n);for(auto&i:a)cin>>i;return a;}()
#endif

//Pre-runs
auto __PR=(cout<<fixed<<setprecision(COUT_FP),0);
#if !(DEBUG)
auto __PR_NDB=(ios::sync_with_stdio(0),cin.tie(0),cout.tie(0));
#endif
void solve();
signed main(){
	for(int ti=1,t=TC;ti<=t;ti++)
		print(TC_OUT_PREFIX),
		solve();
#if CHECK_INPUT
	assert(cin.get()=='\n');
	assert(cin.get()==EOF);
#endif
}
//

using namespace __gnu_pbds;
using namespace __gnu_cxx;

int __RANDOM=i64(new int)^time(0);
struct randomhasher{int operator()(int x)const{return x^__RANDOM;}};
template<class K,class V> using HashMap=gp_hash_table<K,V,randomhasher>;
//MLE or RLE or WA 날땐 cc_hash_table or unordered_map 사용

template<class T,class CMP=less<>,class Policy=pairing_heap_tag>
struct pbds_pq
:public __gnu_pbds::priority_queue<T,CMP,Policy>{
	pbds_pq(){}
	pbds_pq(pbds_pq&& r){this->swap(r);}
	void operator=(pbds_pq&& r){this->swap(r);}
};

//NOTE: pbds_tree.join은 중복키 있으면 join_error 예외발생
template<class T>
struct pbds_set
:public tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>{
	pbds_set(){}
	pbds_set(pbds_set&& r){this->swap(r);}
	void operator=(pbds_set&& r){this->swap(r);}
};
template<class K,class V>
struct pbds_map
:public tree<K,V,less<K>,rb_tree_tag,tree_order_statistics_node_update>{
	pbds_map(){}
	pbds_map(pbds_map&& r){this->swap(r);}
	void operator=(pbds_map&& r){this->swap(r);}
};
template<class T> struct pbds_multiset{
	pbds_set<pair<T,int>> s;
	auto begin()const{return s.begin();}
	auto end()const{return s.end();}
	auto find(const T& v)const{
		auto it=s.lb({v,0});
		return it->fi==v?it:s.end();}
	auto insert(const T& v){return s.insert({v,counter++});}
	auto erase(const typename pbds_set<pair<T,int>>::iterator& it){return s.erase(it);}
	int order_of_key(const T& v,bool ub=true)const{return s.order_of_key({v,ub?counter:0});}
	auto find_by_order(int ord)const{return s.find_by_order(ord);}
	int count(const T& v)const{return order_of_key(v)-order_of_key(v-1);}
	int size()const{return sz(s);}
private:
	int counter=0;
};
int k;

struct Hull{
	int zp=0;
	PQ<int> pq;//slopes
	void minkowski_sum(Hull&& r){
		zp+=r.zp;
		while(sz(r.pq))
			pq.push(r.pq.top()),r.pq.pop();
		while(pq.size()>k)
			pq.pop();
	}
	//add a*min(i,b-i) to graph
	void update(int a, int b){
		zp+=0; //a*b should be even
		int i=0;
		PQ<int> z;
		while(sz(pq)){
			int x=pq.top(); pq.pop();
			if(i*2<b)
				z.push((i+1)*2<=b?x+a:x);
			else
				z.push(x-a);
			i++;
		}
		swap(z,pq);
		while(pq.size()>k)
			pq.pop();
	}
	int get(){
		if(pq.size()<k)
			return 0;
		int sum=0;
		while(sz(pq))
			sum+=pq.top(),pq.pop();
		return sum;
	}
};

void solve(){
	auto[n,k]=input<int,2>();
	::k=k;
	Arr<Arr<pint>> g(n);
	for(int i=0;i<n-1;i++){
		auto[u,v,w]=input<int,3>();
		u--,v--;
		g[u].emplace_back(v,w);
		g[v].emplace_back(u,w);
	}
	int ans=0;
	func(Hull,dfs,int x,int p){
		Hull a;
		a.pq.push(0);
		sort(g[x].begin(),g[x].end(),val2cmp([&](pint i){return -sz(g[i.first]);}));
		for(auto [y,w]:g[x]){
			if(y!=p){
				auto b=dfs(y,x);
				b.update(2*w,k);
				a.minkowski_sum(move(b));
			}
		}
		ans=max(ans,a.get());
		return a;
	};
	dfs(0,0);
	println(ans);
}