#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 n;
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;
}

bool validan(ll aaa){
    bool pos[25];
    for(ll i=0;i<25;i++) pos[i]=false;
    //ll bitmaskp=1;
    for(ll i=1;i<=n;i++){
        if(aaa&1){
            pos[i]=true;
            for(ll j=0;j<pov[i].size();j++){
                pos[pov[i][j]]=true;
            }
        }
        aaa/=2;
    }
    for(ll i=0;i<25;i++) if(!pos[i]) return false;
    return true;
}

ll validan2(ll aaa){
    ll rez=0;
    for(ll i=1;i<=n;i++){
        if(aaa&1){
            rez+=c[i];
        }
        aaa/=2;
    }
    return rez;
}

ll dist[25];

void bfs(ll ind){
    queue<ll> red;
    red.push(ind);
    while(!red.empty()){

    }
}

void ispisi(ll aaa){
    for(ll i=1;i<=n;i++){
        if(aaa&1){
            break;
        }
        aaa/=2;
    }
    bfs(i);
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
    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(n<=20){
        ll res=INF;
        ll res2;
        for(ll i=1;i<=(2LL)<<20;i++){
            if(validan(i)){
                res=min(validan2(i),res);
                res2=i;
            }
        }
        cout<<res<<"\n";
        ispisi(res2);
    }else if(tg2){
        dp[1]=c[1];
        dp2[1]=1;
        dp3[1]=0;
        for(ll i=2;i<=n;i++){
            if(dp2[i-1]){
                if(dp[i-1]<=dp[i-2]+c[i]){
                    dp2[i]=0;
                }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 pom;
                if(i>=3) pom=dp[i-3]+c[i-1];
                else pom=INF;
                if(pom>=dp[i-1]+c[i]){
                    dp2[i]=1;
                    dp3[i]=i-2;
                }else{
                    dp2[i]=0;
                }
                dp[i]=min(dp[i-1]+c[i],pom);
            }
        }
        cout<<dp[n]<<"\n";
        vector<ll> neparni;
        vector<ll> parni;
        ll ind=(dp2[n]?n:n-1);
        while(ind>0){
            if(ind%2==0) parni.pb(ind);
            else neparni.pb(ind);
            ind=dp3[ind];
        }
        cerr<<"\n\n\n\n"<<dp2[3]<<"\n\n\n\n";
        cout<<parni.size()<<"\n";
        for(ll i=0;i<parni.size();i++) cout<<parni[i]<<" ";
        cout<<"\n"<<neparni.size();
        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);
    }else cout<<"0\n0\n0";
}