#include "roads.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 2005;
int32_t n;
vector<pair<int32_t,int32_t>> g[maxn];
vector<int> dp[maxn][maxn], mark[maxn][maxn];
int sol(int32_t u, int32_t q, int32_t id, int32_t ant, int32_t k) {
if(mark[u][q][id] == k) return dp[u][q][id];
mark[u][q][id] = k;
if(id == g[u].size()) {
if(q > k) return dp[u][q][id] = inf;
return dp[u][q][id] = 0;
}
int v = g[u][id].fr;
int w = g[u][id].sc;
if(v == ant) {
return dp[u][q][id] = sol(u,q,id+1,ant,k);
}
return dp[u][q][id] = min(sol(u,q,id+1,ant,k)+sol(v,g[v].size(),0,u,k),w+sol(u,q-1,id+1,ant,k)+sol(v,g[v].size()-1,0,u,k));
}
vector<int> minimum_closure_costs(int32_t N, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
n = N;
int sm = 0;
for(int i = 0; i < n-1; i++) {
g[U[i]+1].pb(mp(V[i]+1,W[i]));
g[V[i]+1].pb(mp(U[i]+1,W[i]));
sm+= W[i];
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= n+1; j++) {
for(int k = 0; k <= g[i].size()+10; k++) {
dp[i][j].pb(0);
mark[i][j].pb(0);
}
}
}
vector<int> ans;
ans.pb(sm);
for(int i = 1; i <= 3; i++) {
ans.pb(sol(1,g[1].size(),0,0,i));
}
for(int i = 4; i <= n-1; i++) {
ans.pb(0);
}
return ans;
}
