#include <bits/stdc++.h>
#define ll long long int
#define MAX_N 200005

using namespace std;

int n;
int a[MAX_N];
vector<int> graph[MAX_N];
ll min_cost = numeric_limits<ll>::max();
ll ans = -1;
int colornode[MAX_N];
ll dp[MAX_N];

void computecost(int x) {
    ll curr_cost = 0;
    bool visited[n];
    for(int i = 0; i < n; i++) {
        if(x & (1 << i)) {
            curr_cost += a[i];
            visited[i] = true;
        } else {
            visited[i] = false;
        }
    }
    for(int i = 0; i < n; i++) {
        bool possible = false;
        for(auto iter : graph[i]) {
            if(visited[iter] || visited[i]) {
                possible = true;
            }
        }
        if(!possible) {
            return ;
        }
    }
    if(curr_cost < min_cost) {
        min_cost = curr_cost;
        ans = x;
    }
}

void dfs(int curr_node, int prev_node, int c) {
    colornode[curr_node] = c;
    for(auto iter_node : graph[curr_node]) {
        if(iter_node == prev_node) {
            continue;
        }
        if(colornode[iter_node] == -1) {
            dfs(iter_node, curr_node, 1 - c);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    if(n <= 20) {
        for(int i = 0; i < (1 << n); i++) {
            computecost(i);
        }
        cout << min_cost << "\n";
        fill(colornode, colornode + n, -1);
        dfs(0, -1, 0);
        int r = 0, b = 0;
        vector<int> red, blue;
        for(int i = 0; i < n; i++) {
            if(colornode[i] == 0 && (ans & (1 << i))) {
                red.push_back(i + 1);
                r++;
            } else if(ans & (1 << i)){
                blue.push_back(i + 1);
                b++;
            }
        }
        cout << r << "\n";
        for(auto iter : red) {
            cout << iter << " ";
        }
        if(r > 0) {
            cout << "\n";
        }
        cout << b << "\n";
        for(auto iter : blue) {
            cout << iter << " ";
        }
    } else if(graph[0].size() == n - 1){
        ll sumleft = 0;
        for(int i = 1; i < n; i++) {
            sumleft += a[i];
        }
        if(sumleft > a[0]) {
            cout << a[0] << "\n";
            cout << "1\n1\n0";
        } else {
            cout << sumleft << "\n";
            cout << n - 1 << "\n";
            for(int i = 2; i <= n; i++) {
                cout << i << " ";
            }
            cout << "\n0";
        }
    } else {
        ll ans1 = numeric_limits<ll>::max();
        ll ans2 = numeric_limits<ll>::max();
        dp[0] = 0;
        dp[1] = a[0];
        dp[2] = a[1];
        vector<int> try1, try2;
        for(int i = 3; i <= n; i++) {
            dp[i] = min(dp[i - 1], min(dp[i - 2], dp[i - 3])) + a[i - 1];
        }
        ans1 = min(dp[n], dp[n - 1]);
        int ptr;
        if(ans1 == dp[n - 1]) {
            ptr = n - 1;
        } else {
            ptr = n;
        }
        while(ptr > 0) {
            try1.push_back(ptr);
            if(ptr - 3 >= 0) {
                if(dp[ptr - 3] <= dp[ptr - 2] && dp[ptr - 3] <= dp[ptr - 1]) {
                    ptr -= 3;
                } else if(dp[ptr - 2] <= dp[ptr - 3] && dp[ptr - 2] <= dp[ptr - 1]) {
                    ptr -= 2;
                } else {
                    ptr--;
                }
            } else if(ptr - 2 >= 0){
                if(dp[ptr - 2] <= dp[ptr - 1]) {
                    ptr -= 2;
                } else {
                    ptr--;
                }
            } else {
                ptr--;
            }
        }
        reverse(a, a + n);
        dp[0] = 0;
        dp[1] = a[0];
        dp[2] = a[1];
        for(int i = 3; i <= n; i++) {
            dp[i] = min(dp[i - 1], min(dp[i - 2], dp[i - 3])) + a[i - 1];
        }
        ans2 = min(dp[n], dp[n - 1]);
        if(ans2 == dp[n - 1]) {
            ptr = n - 1;
        } else {
            ptr = n;
        }
        while(ptr > 0) {
            try2.push_back(n - ptr + 1);
            if(ptr - 3 >= 0) {
                if(dp[ptr - 3] <= dp[ptr - 2] && dp[ptr - 3] <= dp[ptr - 1]) {
                    ptr -= 3;
                } else if(dp[ptr - 2] <= dp[ptr - 3] && dp[ptr - 2] <= dp[ptr - 1]) {
                    ptr -= 2;
                } else {
                    ptr--;
                }
            } else if(ptr - 2 >= 0){
                if(dp[ptr - 2] <= dp[ptr - 1]) {
                    ptr -= 2;
                } else {
                    ptr--;
                }
            } else {
                ptr--;
            }
        }
        vector<int> red, blue;
        if(ans1 < ans2) {
            for(auto iter : try1) {
                if(iter % 2 == 0) {
                    red.push_back(iter);
                } else {
                    blue.push_back(iter);
                }
            }
        } else {
            for(auto iter : try2) {
                if(iter % 2 == 0) {
                    red.push_back(iter);
                } else {
                    blue.push_back(iter);
                }
            }
        }
        cout << min(ans1, ans2) << "\n";
        cout << red.size() << "\n";
        for(auto iter : red) {
            cout << iter << " ";
        }
        if(red.size() > 0) {
            cout << "\n";
        }
        cout << blue.size() << "\n";
        for(auto iter : blue) {
            cout << iter << " ";
        }
    }
    return 0;
}