#include <bits/stdc++.h>

using namespace std;

int main()
{
    cin.tie(0);
    cout.tie(0);
    int n,u,v,p1=1,p2=1,pom,z=1;
    long long s=0,s1=0,s2=0;
    cin>>n;
    vector<long long>a(n+1);
    vector<long long>d(n+1);
    vector<int>p(n+1);
    int R[n],B[n],nr=0,nb=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        s+=(long)a[i];
    }
    a[n]=0;
    for(int i=0;i<n-1;i++)
    {
        cin>>u>>v;
        if(u!=1 and v!=1)p1=0;
    }
    if(p1==1)
    {
        if(a[0]<s-a[0])
        {
            cout<<a[0]<<endl;
            cout<<1<<endl;
            cout<<1<<endl;
            cout<<0<<endl;
        }
        else
        {
            cout<<s-a[0]<<endl;
            cout<<n-1<<endl;
            for(int i=2;i<=n;i++)
                cout<<i<<" ";
            cout<<endl;
            cout<<0<<endl;
        }
    }
    else if(p2==1)
    {
     d[0]=a[0];
     d[1]=a[1];
     p[0]=-1;
     p[1]=-1;
     for(int i=2;i<=n;i++)
     {
         if(d[i-1]<d[i-2])
         {
             d[i]=d[i-1]+a[i];
             p[i]=i-1;
         }
         else
         {
             d[i]=d[i-2]+a[i];
             p[i]=i-2;
         }
     }
     cout<<d[n]<<endl;
     pom=n;
     while(pom!=-1)
     {
         if(pom-p[pom]==1)
            z=-z;
         pom=p[pom];
         if(pom!=-1)
         {
         if(z==1)
          {
              R[nr]=pom+1;
              nr++;
          }
         else
          {
              B[nb]=pom+1;
              nb++;
          }
         }
     }
     cout<<nr<<endl;
     for(int i=0;i<nr;i++)
        cout<<R[i]<<" ";
     cout<<endl;
     cout<<nb<<endl;
     for(int i=0;i<nb;i++)
        cout<<B[i]<<" ";
    }
}