#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define pb push_back
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 1e5 + 5;
int main(){
    ios;
    int n;
    cin>>n;
    vector<ll> a(n+1);
    for(int i = 1;i<=n;i++)cin>>a[i];
    vector<vector<int>> g(n + 1);
    bool podzadatak1 = true;
    bool podzadatak2 = true;
    for(int i = 0;i < n - 1;i++){
        int u, v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
        if(u!=1&&v!=1)podzadatak1 = false;
        if(abs(u-v)>1)podzadatak2 = false;
    }
    if(podzadatak1){
        ll r1 = a[1];
        ll r2 = 0;
        for(int i = 2;i<=n;i++)r2+=a[i];
        if(r1<=r2){
            cout<<r1<<endl;
            cout<<1<<endl;
            cout<<1<<endl;
            cout<<0<<endl;
        }
        else{
            cout<<r2<<endl;
            cout<<n-1<<endl;
            for(int i = 2;i<=n;i++)cout<<i<<" ";
            cout<<endl;
            cout<<0<<endl;
        }
        return 0;
    }
    if(podzadatak2){
        vector<ll> dp(n+1, LLONG_MAX);
        dp[1]=a[1];
        dp[2]=a[2];
        for(int i = 3;i<=n;i++){
            if(i==2)dp[i]=dp[i-1]+a[i];
            else{
                dp[i]=a[i] + min(dp[i-1], dp[i-2]);
            }
        }
        for(int i = 1;i<=n;i++)cout<<dp[i]<<" ";
        cout<<endl;
        ll res = dp[n];
        ll tr = n;
        if(res>dp[n-1]){
            res = dp[n-1];
            tr = n-1;
        }
        vector<int> p[2];
        while(tr>2){
            p[tr%2].pb(tr);
            dp[tr]-=a[tr];
            if(dp[tr-2]==dp[tr])tr-=2;
            else tr--;
        }
        p[tr%2].pb(tr);
        cout<<res<<endl;
        cout<<p[0].size()<<endl;
        if(p[0].size()>0){
            for(int x : p[0])cout<<x<<" ";
            cout<<endl;
        }
        else cout<<endl;
        cout<<p[1].size()<<endl;
        for(int x : p[1])cout<<x<<" ";
        cout<<endl;
        //pomozi Boze
    }

}