#include <iostream>

using namespace std;

int a[200001];
long long obojeno[200001];
string s1p, s2p, s3p, s1c, s2c, s3c;
int n1p, n2p, n3p, n1c, n2c, n3c;

void oboji(int n)
{
    obojeno[1] = a[1];
    obojeno[2] = a[2];
    s1c = "1";
    s1p = "";
    s2p = "2";
    s2c = "";
    n1c = 1;
    n1p = 0;
    n2c = 0;
    n2p = 1;
    if(obojeno[1] < obojeno[2])
    {
        obojeno[3] = obojeno[1] + a[3];
        s3c = "1 3";
        s3p = "";
        n3c = 2;
        n3p = 0;
    }
    else
    {
        obojeno[3] = obojeno[2] + a[3];
        s3p = "2";
        s3c = "3";
        n3c = 1;
        n3p = 1;
    }
    for(int i = 4; i <= n; i++)
    {
        if(obojeno[i-3] < obojeno[i-2])
        {
            obojeno[i] = obojeno[i-3] + a[i];
            string sc, sp;
            int tc, tp;
            if(i%2 == 1)
            {
                sc = s1c + " " + to_string(i);
                tc = n1c + 1;
                sp = s1p;
                tp = n1p;
            }
            if(i%2 == 0)
            {
                sp = s1p + " " + to_string(i);
                tp = n1p + 1;
                sc = s1c;
                tc = n1c;
            }
            n1c = n2c;
            n1p = n2p;
            s1c = s2c;
            s1p = s2p;
            n2c = n3c;
            n2p = n3p;
            s2c = s3c;
            s2p = s3p;
            n3c = tc;
            n3p = tp;
            s3c = sc;
            s3p = sp;
        }
        else
        {
            obojeno[i] = obojeno[i-2] + a[i];
            string sc, sp;
            int tc, tp;
            if(i%2 == 1)
            {
                sc = s2c + " " + to_string(i);
                tc = n2c + 1;
                sp = s2p;
                tp = n2p;
            }
            if(i%2 == 0)
            {
                sp = s2p + " " + to_string(i);
                tp = n2p + 1;
                sc = s2c;
                tc = n2c;
            }
            n1c = n2c;
            n1p = n2p;
            s1c = s2c;
            s1p = s2p;
            n2c = n3c;
            n2p = n3p;
            s2c = s3c;
            s2p = s3p;
            n3c = tc;
            n3p = tp;
            s3c = sc;
            s3p = sp;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    int sl = 0;
    for(int i = 0; i < n-1; i++)
    {
        int x, y;
        cin >> x >> y;
        if(x > y)
            swap(x, y);
        if(x == 1 && y > 2)
            sl = 1;
    }
    if(sl == 1)
    {
        long long s = 0;
        for(int i = 2; i <= n; i++)
            s += a[i];
        if(s >= a[1])
            cout << a[1] << endl << 1 << endl << 1 << endl << 0;
        else
        {
            cout << s << endl << n-1 << endl;
            for(int i = 2; i <= n; i++)
                cout << i << " ";
            cout << endl << 0;
        }
    }
    else
    {
        oboji(n);
        if(obojeno[n] > obojeno[n-1])
        {
            cout << obojeno[n-1] << endl << n2c << endl << s2c << endl << n2p << endl << s2p;
        }
        else
        {
            cout << obojeno[n] << endl << n3c << endl << s3c << endl << n3p << endl << s3p;
        }
    }
    return 0;
}