#include<stdio.h>
#define fin  "asmax.in"
#define fout "asmax.out"
#define Nmax 16001
#define Inf 0x3f3f3f3f
int n,m,v[Nmax],list[2*Nmax][2],adr[Nmax],viz[Nmax];
int best;

FILE *in,*out;

inline void swap (int &a,int &b) { int aux; aux=a; a=b; b=aux; }

void qsort(int st,int dr) {
int i,j,m;
	i=st; j=dr;
	m=list[(i+j)/2][0];
	do {
		while (list[i][0]<m) ++i;
		while (list[j][0]>m) --j;
		if (i<=j) {
			swap(list[i][0],list[j][0]);
			swap(list[i][1],list[j][1]);
			++i; --j;
		}
	} while (i<j);

	if (i<dr) qsort(i,dr);
	if (j>st) qsort(st,j);	
}

void df(int nod) {
int i;
	viz[nod]=1;
	
	for (i=adr[nod];list[i][0]==nod;++i) 

		if (!viz[list[i][1]]) {
			
			df(list[i][1]);

			if (v[list[i][1]]>0) v[nod]+=v[list[i][1]];
		}

}

int main() {
int i,j,a,b;
	in=fopen(fin,"r"); out=fopen(fout,"w");
	fscanf(in,"%i%i",&n,&n);
       	++n; m=2*n-2;
	
	for (i=1;i<=n;++i) fscanf(in,"%i",&v[i]);
	
	for (i=1;i<n;++i) {
		fscanf(in,"%i%i",&a,&b);
		list[i][0]=a;
		list[i][1]=b;
		list[n+i-1][0]=b;
		list[n+i-1][1]=a;
	}

	qsort(1,m);

	for (i=1;i<=m;) {
		
		for (j=i;list[j][0]==list[i][0] && j<=m;++j);
		adr[list[i][0]]=i;
		i=j;
	}
		
	df(1);

	best=-Inf;

	for (i=1;i<=n;++i) {
		printf("%i ",v[i]);
		if (v[i]>best) {
			best=v[i];
		}
	}
	
	printf("\n");

	fprintf(out,"%i\n",best);

	fclose(in); fclose(out);

	return 0;
}