#include<bits/stdc++.h>
using namespace std;
int main(){

    int n;
    cin>>n;

    int niz[n+5];
    vector<vector<int> > v( n );

    for(int i=0;i<n;i++){
        cin>>niz[i];
    }

    int a,b;
    for(int i=0;i<n-1;i++){

        cin>>a>>b;

        a--;
        b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int vlcn[n+5];
    bool bul1 = true;

    if(v[0].size() != 1){
        bul1 = false;
    }
    for(int i=1;i<n-1;i++){

        if(v[i].size() != 2){
            bul1 = false;
            break;
        }
    }
    if(v[n-1].size() != 1){
        bul1 = false;
    }

    if(v[0].size() == n-1){

        int u=0;
        for(int i=1;i<n;i++){

            u += niz[i];
        }

        if(niz[0] <= u){

            cout<<niz[0]<<endl;
            cout<<1<<endl;
            cout<<1<<endl;
            cout<<0<<endl;
        }
        else{

            cout<<u<<endl;
            cout<<n-1<<endl;
            for(int i=1;i<n;i++){

                cout<<i+1<<" ";
            }
            cout<<endl;
            cout<<0;
        }
    }
    else if(bul1){

        int u1=0;
        int u2=0;
        int u3=0;

        int modd = n%3;

        for(int i=0;i<n;i=i+3){

            u1 += niz[i];
        }
        for(int i=1;i<n;i=i+3){

            u2 += niz[i];
        }
        for(int i=2;i<n;i=i+3){

            u3 += niz[i];
        }

        ////////////////////

        if(modd == 0){

            u1 += min(niz[n-2],niz[n-1]);
            u3 += min(niz[0],niz[1]);
            bool jed = false;

            if(u1 == u2 && u2 == u3){

                jed = true;
            }

            if(u2<=u1 && u2<=u3){

                cout<<u2<<endl;
                cout<<n/3<<endl;
                for(int i=1;i<n;i=i+3){
                    cout<<i+1<<" ";
                }
                cout<<endl;
                cout<<0;
            }
            else if(jed == false && u1<=u2 && u1<=u3){

                cout<<u1<<endl;
                cout<<n/3 + 1<<endl;
                for(int i=0;i<n;i=i+3){
                    cout<<i+1<<" ";
                }
                if(niz[n-2] < niz[n-1]){
                    cout<<n-1<<endl;
                }
                else{
                    cout<<n<<endl;
                }
                cout<<0;
            }
            else if( jed == false && u3<=u1 && u3<=u2){

                cout<<u3<<endl;
                cout<<n/3 + 1<<endl;
                if(niz[0] > niz[1]){
                    cout<<2<<" ";
                }
                else{
                    cout<<1<<" ";
                }
                for(int i=2;i<n;i=i+3){
                    cout<<i+1<<" ";
                }
                cout<<endl;
                cout<<0;
            }
        }

        /////////////////

        else if(modd == 1){

            u2 += min(niz[n-2],niz[n-1]);
            u3 += min(niz[0],niz[1]);
            bool jed = false;

            if(u1 == u2 && u2 == u3){

                jed = true;
            }

            if(u1<=u2 && u1<=u3){

                cout<<u1<<endl;
                cout<<n/3 + 1<<endl;
                for(int i=0;i<n;i=i+3){
                    cout<<i+1<<" ";
                }
                cout<<endl;
                cout<<0;
            }
            else if( jed == false && u2<=u1 && u2<=u3){

                cout<<u2<<endl;
                cout<<n/3 + 1<<endl;
                for(int i=1;i<n;i=i+3){
                    cout<<i+1<<" ";
                }
                if(niz[n-2] < niz[n-1]){
                    cout<<n-1<<endl;
                }
                else{
                    cout<<n<<endl;
                }
                cout<<0;
            }
            else if( jed == false && u3<=u1 && u3<=u2){

                cout<<u3<<endl;
                cout<<n/3 + 1<<endl;
                if(niz[0] > niz[1]){
                    cout<<2<<" ";
                }
                else{
                    cout<<1<<" ";
                }
                for(int i=2;i<n;i=i+3){
                    cout<<i+1<<" ";
                }
                cout<<endl;
                cout<<0;
            }

            ///////////

        }
        else if(modd == 2){

            u3 += min(niz[n-2],niz[n-1]);
            u3 += min(niz[0],niz[1]);
            bool jed = false;

            if(u1 == u2 && u2 == u3){

                jed = true;
            }

            if(u1<=u2 && u1<=u3){

                cout<<u1<<endl;
                cout<<n/3 + 1<<endl;
                for(int i=0;i<n;i=i+3){
                    cout<<i+1<<" ";
                }
                cout<<endl;
                cout<<0;
            }
            else if( jed == false && u2<=u1 && u2<=u3){

                cout<<u2<<endl;
                cout<<n/3 + 1<<endl;
                for(int i=1;i<n;i=i+3){
                    cout<<i+1<<" ";
                }
                cout<<endl;
                cout<<0;
            }
            else if(jed == false && u3<=u1 && u3<=u2){

                cout<<u3<<endl;
                cout<<n/3 + 2<<endl;
                if(niz[1] < niz[0]){
                    cout<<2<<" ";
                }
                else{
                    cout<<1<<" ";
                }
                for(int i=2;i<n;i=i+3){
                    cout<<i+1<<" ";
                }
                if(niz[n-2] < niz[n-1]){
                    cout<<n-1<<endl;
                }
                else{
                    cout<<n<<endl;
                }
                cout<<0;
            }
        }

    }
}