首先有不使用任何水晶的答案为 $2\sum w_i$，使用 $k$ 个水晶就可以选 $k$ 条点不交的竖直路径减掉贡献。

$k=1$ 时一定选取最长竖直路径；$k=2$ 时，要么在 $k=1$ 的基础上选取一条新的路径，要么把 $k=1$ 那条路径的某条边断掉并从父亲点再往下继续扩展一条路径，往后同理。

可以发现选取新路径时，新路径的上端点的父亲一定是之前路径上出现过的点，所以我们可以修改流程：$k=2$ 开始，每次选择一个被路径覆盖过的点，在它的未被路径覆盖过的儿子中新选择一条路径，或断开自己当前所在路径上通向儿子的边并连上一条以一个未被路径覆盖过的儿子为上端点的路径，假设当前路径上通向儿子的边的边权为 $x$，连向第 $i$ 个未被覆盖过的儿子的边的边权为 $w_i$，以第 $i$ 个未被覆盖过的儿子为上端点的最长竖直路径长度为 $d_i$，则可以获得 $\max\{(0,w_i-x)+d_i\}$ 的贡献，不难得到 $x$ 一定是通向已经被覆盖过的所有儿子的边中的最大边权。

所以我们只需要处理出每个点向下选择路径的优先级及贡献，再用一个优先队列维护每次该从哪个点向下选择路径即可。处理优先级时，因为贡献为 $\max\{(0,w_i-x)+d_i\}$，所以每次一定是选剩下的当中 $w_i+d_i$ 最大的，或 $d_i$ 最大的，只需要分别排序，然后每次取较大的就可以了。

::::info[时间复杂度 $O(n\log n)$，点此查看代码]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=500005;
int n,k,ans,all,cnt[N],vis[N];
priority_queue<pair<int,int>> q;
vector<pair<int,int>> v[N],dif[N];
int dfs(int x,int fa){
	if(fa&&v[x].size()==1)  return 0;
    vector<tuple<int,int,int>> re1,re2;
	for(auto [y,w]:v[x]){
		if(y==fa)  continue;
		int tmp=dfs(y,x);
        re1.emplace_back(tmp,y,w);
        re2.emplace_back(w+tmp,y,w);
	}
    int cnt1=0,cnt2=0,mx=0,m=re1.size();
    sort(re1.begin(),re1.end(),greater<>());
    sort(re2.begin(),re2.end(),greater<>());
    for(int i=0;i<m;i++){
        while(vis[get<1>(re1[cnt1])])  cnt1++;
        while(vis[get<1>(re2[cnt2])])  cnt2++;
        auto [tmp1,num1,w1]=re1[cnt1];
        auto [tmp2,num2,w2]=re2[cnt2];
		tmp1+=max(0ll,w1-mx),tmp2-=min(w2,mx);
        if(tmp1>tmp2){
            mx=max(mx,w1),vis[num1]=1;
            dif[x].emplace_back(tmp1,num1);
        }
        else{
            mx=max(mx,w2),vis[num2]=1;
            dif[x].emplace_back(tmp2,num2);
        }
    }
	return get<0>(re2[0]);
}
void work(int x){
	if(cnt[x]>=dif[x].size())  return;
	auto [dis,y]=dif[x][cnt[x]++];work(y);
	if(cnt[x]>=dif[x].size())  return;
	auto [ndis,ny]=dif[x][cnt[x]];
	q.emplace(ndis,x);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>k;
	for(int i=1,x,y,w;i<n;i++){
		cin>>x>>y>>w,all+=w*2;
		v[x].emplace_back(y,w);
		v[y].emplace_back(x,w);
	}
    dfs(1,0),q.emplace(dif[1][0].first,1);
	for(int i=1;i<=k;i++){
		if(!q.empty()){
			auto [dis,x]=q.top();
			q.pop(),work(x),ans+=dis;
		}
		cout<<all-ans<<"\n";
	}
}

::::