#include<fstream>
using namespace std;
int n,v[16005],cost[16005],maxim;
int grad[16005],vizitat[16005],t[16005];
struct nod{
	int info;
    nod *next;};
nod *g[16005];	
void dfs(int k);
void adauga(int a,int b);
int costulmax(int k);
ofstream fout("asmax.out");
int main ()
{
	ifstream fin("asmax.in");
	fin>>n;
	int i;
	for(i=1;i<=n;i++)
		fin>>v[i],cost[i]=v[i];
	for(i=1;i<n;i++)
	{
		int a,b;
		fin>>a>>b;
		adauga(a,b);
		adauga(b,a);
		grad[a]++;
		grad[b]++;
	}
	int pp=0,radacina;
	for(i=1;i<=n && pp==0;i++)
		if(grad[i]==1)
			radacina=i,pp=1;
	
	fout<<radacina<<endl;
	dfs(radacina);
	//sort(cost)
	for(i=1;i<=n;i++)
	   fout<<t[i];
	//for(nod *p=g[2])
	return 0;
}
void dfs(int k)
{
	vizitat[k]=1;
	for(nod *p=g[k];p;p=p->next)
		if(vizitat[p->info]==0)
			t[p->info]=k,dfs(p->info);
	cost[k]=costulmax(k);
}
int costulmax(int k)
{
	fout<<k<<" ";
	int suma=cost[k];
	for(nod *p=g[k];p;p=p->next)
		if(p->info!=t[k])
			if(suma+cost[p->info]>suma)
				suma+=v[p->info];
    fout<<suma<<endl;
	return suma; 
}
void adauga(int a,int b)
{
	nod *p;
	p=new nod;
	p->info=b;
	p->next=g[a];
	g[a]=p;
}