#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define ll long long
const int N = 1<<17, M = 2005;
ll vl[N][2], dp[M][M][2];
vector<pair<int, int>> nei[N];
vector<ll> sub1(int n, vector<int> U, vector<int> V, vector<int> W){
sort(rbegin(W), rend(W));
vector<ll> Ans(n, 0);
for (int i : W)
Ans[0] += i;
for (int i=1;i<=W.size();i++)
Ans[i] = Ans[i-1] - W[i-1];
return Ans;
}
vector<ll> sub2(int n, vector<int> U, vector<int> V, vector<int> W){
vector<ll> Ans(n, 0);
for (int i : W)
Ans[0] += i;
for (int i=1;i<n;i++){
vl[i][1] = vl[i-1][0];
vl[i][0] = min(vl[i-1][0], vl[i-1][1]) + W[i-1];
}
Ans[1] = min(vl[n-1][0], vl[n-1][1]);
return Ans;
}
void dfs(int u, int p, int k){
for (auto [i, w] : nei[u]){
if (i != p)
dfs(i, u, k);
}
for (int j=1;j<k;j++){
ll S = 0, s2 = 0;
multiset<ll> ms;
for (auto [i, w] : nei[u]){
if (i == p)
continue;
ll v1 = min(dp[i][j][0], dp[i][j][1]) + w, v2 = dp[i][j][0];
S += v1;
if (v1 > v2)
ms.insert(v1 - v2), s2 += v1 - v2;
if (ms.size() > j)
s2 -= *begin(ms), ms.erase(begin(ms));
}
if (ms.size() == j)
dp[u][j][1] = S - s2, dp[u][j][0] = S - s2 + *begin(ms);
else
dp[u][j][0] = dp[u][j][1] = S - s2;
}
// cout<<u<< " :: ";
// for (int j=1;j<k;j++)
// cout<<"{"<<dp[u][j][0]<<','<<dp[u][j][1]<<"} ";
// cout<<endl;
}
vector<ll> sub3(int n, vector<int> U, vector<int> V, vector<int> W){
for (int i=0;i<n-1;i++){
nei[U[i]].push_back({V[i], W[i]});
nei[V[i]].push_back({U[i], W[i]});
}
dfs(0, -1, n);
vector<ll> Ans(n, 0);
for (int j=1;j<n;j++)
Ans[0] += W[j-1], Ans[j] = min(dp[0][j][0], dp[0][j][1]);
return Ans;
}
vector<ll> minimum_closure_costs(int n, vector<int> U, vector<int> V, vector<int> W){
bool t = 1;
for (int i=0;i<n-1;i++)
t &= U[i] == 0;
if (n <= 2000)
return sub3(n, U, V, W);
if (t)
return sub1(n, U, V, W);
return sub2(n, U, V, W);
}
