#include "roads.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib>
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
//#define int long long
#define double long double
/*
*****
check if function has a return value?
*****
*/
const int mxn=1e5,inf=1e9,minf=-1e9,Mxn=1e7;
ll dp[mxn+10][2];
vector<pii>adj[mxn+10];
int k;
void solve(int cur,int p){
ll sum=0;
vector<ll>v;
for(auto i:adj[cur]){
if(i.f==p)continue;
solve(i.f,cur);
sum+=dp[i.f][1]+i.s;
v.pb(dp[i.f][0]-dp[i.f][1]-i.s);//del all
}
dp[cur][0]=sum;
sort(all(v));//free sum
int cc=0;
while(cc<v.size()&&cc<k-1&&v[cc]<0)dp[cur][0]+=v[cc],cc++;
dp[cur][1]=dp[cur][0];
if(k&&cc<v.size()&&v[cc]<0)dp[cur][1]+=v[cc];
//cout<<cur<<" "<<dp[cur][0]<<" "<<dp[cur][1]<<"LL\n";
}
int pa[mxn+10];
int find(int u){return (pa[u]==u)?u:pa[u]=find(pa[u]);}
vector<ll> minimum_closure_costs(int N,vector<int>U,vector<int>V,vector<int>W) {
bool sub1=1,sub2=1;
vector<ll>ans;
for(auto i:U)sub1&=(i==0);
for(int i=0;i<N-1;i++)sub2&=(U[i]==i&&V[i]==i+1),pa[i]=i;
if(sub1){
ll sum=0;
sort(all(W));
for(auto i:W)sum+=i;
ans.pb(sum);
for(int i=0;i<N-1;i++)sum-=W.back(),W.pop_back(),ans.pb(sum);
return ans;
}
else if(sub2){
for(int i=0;i<min(N,2);i++)k=i,solve(0,-1),ans.pb(dp[0][1]);
while(ans.size()<N)ans.pb(0);
return ans;
}
else if(N<2000){
for(int i=0;i<N-1;i++){
adj[U[i]].pb({V[i],W[i]});
adj[V[i]].pb({U[i],W[i]});
}
for(int i=0;i<N;i++){
k=i,solve(0,-1);
ans.pb(dp[0][1]);
}
return ans;
}//sub5 dsu??
return ans;
}/*
int32_t main(){
int n;cin>>n;
vector<int>u(n-1),v(n-1),w(n-1);
for(int i=0;i<n-1;i++)cin>>u[i]>>v[i]>>w[i];
vector<ll>ans=minimum_closure_costs(n,u,v,w);
for(auto i:ans)cout<<i<<" ";
cout<<'\n';
}*/
/*
n^2 solution = do dp
dp[0],dp[1]; 0= didnt take par road,1= take par road
we can have atmost k dp[0];
we can sort dp[1]+road-dp[0] cost of all children
then greedy take
*/
