#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <map>

#include <cstring>

#include <iomanip>

const int N = 1e3 + 10;

using namespace std;

const int INF = 0x3f3f3f3f;

using namespace std;

struct node 
{
	int data;
	
	int to;
};
int n , q , u , v , w ;

int dp[N][N] , son[N];

vector<node> vc[N];

void dfs (int u , int fa)
{
	son[u] = 1;
	
	dp[u][1] = 0;
	
	for(int i = 0 ; i < vc[u].size() ; i++)
	{
		int v = vc[u][i].to;
		
		if(v ==fa)continue;
		
		dfs(v , u);
		
		son[u] += son[v];
		
		for(int j = son[u] ; j >= 1 ; j--)
		{
			for(int k = 1 ; k <= min( j - 1 , son[v]) ; k++)
			{
				dp[u][j] = max(dp[u][j] , dp[u][j-k] + dp[v][k] + vc[u][i].data);
			}
		}
	}
}

int main()
{
	cin >> n >> q ;
	
	memset(dp , -INF , sizeof(dp));
	
	for(int i = 1 ; i < n ; i++)
	{
		cin >> u >> v >> w ;
		
		vc[u].push_back((node){w , v});
		
		vc[v].push_back((node){w , u});
	}
	
	dfs( 1 , 0 );
	
	cout << dp[1][q + 1];
	    
	return 0;
}

#include<bits/stdc++.h>
#include<cstring>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define ll long long
using namespace std;
const int N=1e5+10;
const int M=500;
const int inf=0x3f3f3f3f;
struct node
{
	int data;//数据部分 
	int to;//指向的节点 
};
vector<node> vc[N];//v[i]表示第i条链表
int n,q,u,v,w; 
int dp[M][M],son[N];
//dp[i][j]表示以 为根节点  有j个节点时的最优解
void dfs(int u,int fa)
{
	son[u]=1;//计算当前节点的儿子数量
	dp[u][1]=0;
	//每局当前节点的相连边
	for(int i=0;i<vc[u].size();i++)
	{
		int v=vc[u][i].to;//当前节点相连的点
		if(v==fa)continue;//如果相连的点是他的爹 continue
		dfs(v,u);//遍历儿子
		son[u]+=son[v];//儿子数量
		//枚举当前爹节点的儿子数量
		for(int j=son[u];j>=1;j--)
		{
			for(int k=1;k<=min(j-1,son[v]);k++)//当前儿子的节点数 
			{
				dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]+vc[u][i].data);
			}
		 } 
	 } 
 } 
int main()
{
	cin>>n>>q;
	memset(dp,-inf,sizeof dp);
	for(int i=1;i<=n-1;i++)
	{
		cin>>u>>v>>w;
		vc[u].push_back(node{w,v});
		vc[v].push_back(node{w,u});
	}
	dfs(1,0);
	cout<<dp[1][q+1];
	return 0;
}

树状dp

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=105,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
struct edge{
	int to,nt,w;
}e[N<<1];
int h[N],cnt;
void add(int u,int v,int w){
	e[++cnt]={v,h[u],w},h[u]=cnt;
	e[++cnt]={u,h[v],w},h[v]=cnt;
}
int sz[N],n,m;
int dp[N][N];
void dfs(int u,int fa){
	for(int i=h[u];i;i=e[i].nt){
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u);
		sz[u]+=sz[v]+1;
		for(int j=m;~j;j--)
			for(int k=0;k<=min(sz[v],j-1);k++)
				dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k-1]+e[i].w);
	}
}
void solve(){
	//think twice code once
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	dfs(1,0);
	printf("%d\n",dp[1][m]);
}
int main(){
	solve();
	return 0;
}