#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define ll long long
#define INF 1e18
#define maxn 100010
using namespace std;

ll c[maxn];
ll dp[maxn];
bool dp2[maxn];
ll dp3[maxn];
vector<vector<ll>> pov(maxn);

bool cmp(pair<ll,ll> a, pair<ll,ll> b){
    return a.fi>b.fi;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
    ll n; cin>>n;
    bool tg1=1,tg2=1,tg3=1;
    for(ll i=1;i<=n;i++) cin>>c[i];
    for(ll i=2;i<=n;i++) if(c[i]!=c[i-1]) tg3=0;
    for(ll i=1;i<n;i++){
        ll a,b; cin>>a>>b;
        if(a!=1 && b!=1) tg1=0;
        if(abs(a-b)!=1) tg2=0;
        pov[a].pb(b);
        pov[b].pb(a);
    }
    if(tg1){
        ll pom=0;
        for(ll i=2;i<=n;i++) pom+=c[i];
        if(c[1]<=pom) cout<<c[1]<<"\n1\n1\n0";
        else{
            cout<<pom<<"\n"<<n-1<<"\n";
            for(ll i=2;i<=n;i++) cout<<i<<" ";
            cout<<"\n0";
        }
    }else if(tg2){
        dp[1]=c[1];
        dp2[1]=1;
        for(ll i=2;i<=n;i++){
            if(dp2[i-1]){
                if(dp[i-1]<=dp[i-2]+c[i]){
                    dp2[i]=0;
                    dp3[i]=i-1;
                }
                else{
                    dp2[i]=1;
                    dp3[i]=(dp2[i-2]?i-2:i-3);
                }
                dp[i]=min(dp[i-1],dp[i-2]+c[i]);
            }else{
                ll pom2;
                if(i>=3) pom2=dp[i-3]+c[i-1];
                else pom2=INF;
                if(dp[i-2]+c[i]<=pom2){
                    dp2[i]=1;
                    dp3[i]=(dp2[i-2]?i-2:i-3);
                }
                else{
                    dp2[i]=0;
                    dp3[i]=i-1;
                }
                dp[i]=min(dp[i-2]+c[i],pom2);
            }
        }
        cout<<dp[n]<<"\n";
        cerr<<"\n\n\n";
        ll ind=(dp2[n]?n:dp3[n]);
        vector<ll> parni;
        vector<ll> neparni;
        while(ind>0){
            cerr<<ind<<"\n";
            if(ind%2==0) parni.pb(ind);
            else neparni.pb(ind);
            if(ind>dp3[ind]+1) ind=dp3[ind];
            else ind=dp3[ind]-1;
        }
        cerr<<"\n\n\n";
        cout<<parni.size()<<"\n";
        for(ll i=0;i<parni.size();i++) cout<<parni[i]<<" ";
        cout<<"\n"<<neparni.size()<<"\n";
        for(ll i=0;i<neparni.size();i++) cout<<neparni[i]<<" ";
    }else if(tg3){
        vector<pair<ll,ll>> funk;
        for(ll i=1;i<=n;i++) funk.pb({pov[i].size(),i});
        sort(funk.begin(),funk.end(),cmp);
        cout<<"0\n0\n0";
    }else if(n<=20){
        cout<<"0\n0\n0";
    }else cout<<"0\n0\n0";
}