//Problem Link: https://oj.uz/problem/view/APIO21_roads
//APIO 2021 Problem Roads
#include "roads.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);
#define endl \n
#define lbound(x, y) lower_bound(x.begin(), x.end(), y)
#define ubound(x, y) upper_bound(x.begin(), x.end(), y)
#define sortasc(v) sort(v.begin(), v.end())
#define sortdesc(v) sort(v.rbegin(), v.rend())
const lg MOD = 1e9+7, N = 2e5+5, M = 1e7+1;
/*
bitset<N> primes;
lg fast_power(lg n, lg k)
{
if(!k) return 1;
if(k&1) return (fast_power(n, k-1)*n)%MOD;
lg x = fast_power(n, k/2)%MOD;
return (x*x)%MOD;
}
void sieve()
{
primes.set();
primes[0] = primes[1] = 0;
for(lg i = 2; i < N; i++)
{
if(!primes[i]) continue;
for(lg j = i*i; j < N; j += i)
{
primes[j] = 0;
}
}
return;
}
*/
vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W)
{
vector<lg> a(N);
for(int i = 1; i < N; i++) a[i] = W[i-1];
sort(a.begin(), a.end());
for(int i = 1; i < N; i++)
{
a[i] += a[i-1];
}
reverse(a.begin(), a.end());
return a;
}
