#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N=1e5+5;
int n;
vector<pair<int,int>> g[N];
pair<int,int> pa[N];
int s[N],_s;
void dfs(int i){
for(auto&[w,x]:g[i]) if(x!=pa[i].second){
pa[x]={w,i};
dfs(x);
}
s[_s++]=i;
}
std::vector<long long> minimum_closure_costs(int _n,vector<int> U,vector<int> V,vector<int> W){
n=_n;
for(int i=0;i<n-1;++i){
g[U[i]].emplace_back(W[i],V[i]);
g[V[i]].emplace_back(W[i],U[i]);
}
//pa[0]={0,0}; dfs(0);
vector<long long> ret(n,0);
{ // Subtask 2 - Line graph
long long dp[n-1][2]; // 0-notake, 1-take
dp[0][0]=W[0];
dp[0][1]=0;
for(int i=1;i<n-1;++i){
dp[i][0]=min(dp[i-1][0],dp[i-1][1])+W[i];
dp[i][1]=dp[i-1][0];
}
ret[1]=min(dp[n-2][0],dp[n-2][1]);
for(int i=0;i<n-1;++i) ret[0]+=W[i];
}
/*
{ // Subtask 1 - Star graph
ret[n-1]=0;
sort(W.begin(),W.end(),greater<int>());
for(int i=n-2;i>=0;--i){
ret[i]=ret[i+1]+W[i];
}
}
*/
return ret;
}
vector<long long> brute_force(int n,vector<int>U,vector<int>V,vector<int>W){
vector<long long> ret(n,0); ret[1]=3e18;
bool v[n-1];
for(long long msk=0;msk<(1<<(n-1));++msk){
for(int i=0;i<n;++i) v[i]=msk>>i&1;
bool f=0;
for(int i=1;i<n-1&&!f;++i){
if(v[i]&&v[i-1]) f=1;
}
if(f) continue;
long long res=0;
for(int i=0;i<n-1;++i) if(!v[i]){
res+=W[i];
}
ret[1]=min(ret[1],res);
}
for(int i=0;i<n-1;++i) ret[0]+=W[i];
return ret;
}
