#include<stdio.h>
#include<stdlib.h>
#define MAX 100000
#define d_flag 0
typedef int atom;

int deg[MAX+1]={};

typedef struct _cell
{
  atom car;
  struct _cell *cdr;
} cell;

#define NULL_ATOM 0;
cell* make_cell(atom val);
void delete_cell(cell* cp);
cell* cons(atom val,cell* cp,int *err);
atom pop(cell** cpp, int *err);

void print_atom(atom val);
void print_list(cell* cp);

void init_alist(cell** N,int n,int origin){
  int i;
  for(i=0;i<n;i++){
    N[i+origin]=NULL;
  }
}

void read_alist(cell** N,int m){
  int i,u,v,err;

  for(i=0;i<m;i++){
    scanf("%d%d",&u,&v);
    deg[u]++;
    deg[v]++;
    //    if(d_flag)printf("!(u,v):(%d,%d),deg[u]=%d,deg[v]=%d!\n",u,v,deg[u],deg[v]);
    N[u]=cons(v,N[u],&err);
    N[v]=cons(u,N[v],&err);
  }
}

void print_alist(cell** N,int n,int origin){
  printf("Graph.\n");
  int i;
  for(i=0;i<n;i++){
    printf("%2d: ",origin+i);
    print_list(N[i+origin]);
    printf("\n");
  }
}
int C(const void* a,const void* b){
  return (*((int*)a))-(*((int*)b));
}

int Q[MAX];
int head=0;
int tail=0;
void inque(int x){
  Q[tail++]=x;
}
int deque(){
  return Q[head++];
}

void print_que(){
  int i;
  printf("Q:[ ");
  for(i=head;i<tail;i++)
    printf("%d ",Q[i]);
  printf("]\n");
}

typedef struct{
  int v;
  int c;
}pair;
pair asgn[MAX];

int C_pair(const void* a,const void* b){
  return(((pair*)a)->v-((pair*)b)->v);
}

int main(){
  int n,m,flag;
  scanf("%d",&n);

  cell* Nv[n+1];
  init_alist(Nv,n,1);
  read_alist(Nv,n-1);


  int c[n],i;
  for(i=0;i<n;i++){
    scanf("%d",&c[i]);
  }
  qsort(c,n,sizeof(int),C);

  if(d_flag){
    print_alist(Nv,n,1);
    printf("deg: ");
    int j;
    for(j=1;j<=n;j++)
      printf("%d ",deg[j]);
    printf("\n");
  }
  
  long int s=0;
  for(i=0;i<n-1;i++)s+=c[i];
  printf("%d\n",s);

  for(i=1;i<=n;i++){
    if(deg[i]==1)inque(i);
  }
  i=0;
  int x;
  while(tail!=head){
    if(d_flag) print_que();
    x=deque();
    if(deg[x]==0)continue;
    if(d_flag) printf("x: %d",x);
    
    asgn[i].v=x;
    asgn[i].c=c[i];
    i++;
    deg[x]--;
    int y=pop(&(Nv[x]),&flag);
    while(deg[y]==0)y=pop(&(Nv[x]),&flag);
    deg[y]--;
    if(deg[y]==1) inque(y);
    if(d_flag){
      printf("  y: %d\n deg: ",y);
      int j;
      for(j=1;j<=n;j++)
	printf("%d ",deg[j]);
      printf("\n");
    }
  }
  asgn[i].v=x;
  asgn[i].c=c[i];
  

  qsort(asgn,n,sizeof(pair),C_pair);
  for(i=0;i<n;i++){
    printf("%d ",asgn[i].c);
  }

  for(i=1;i<=n;i++)
    delete_cell(Nv[i]);
  return 0;
}




cell* make_cell(atom val)
{
  cell* ncellp=malloc(sizeof(cell));
  if(ncellp!=NULL)
    {
      ncellp->car=val;
      ncellp->cdr=NULL;
    }
  else
    printf("not enough memory.\n");
  return ncellp;
}


void delete_cell(cell* cp)
{
  cell* temp=cp,*next;
  while(temp!=NULL)
    {
      next=temp->cdr;
      free(temp);
      temp=next;
    }
}

cell* cons(atom val,cell* cp,int *err)
{
  cell* top=make_cell(val);
  if(top!=NULL)
    {
      *err=1;
      top->cdr=cp;
      return top;
    }
  *err=0;
  return cp;
}

atom pop(cell** cpp, int *err)
{
  if(*cpp==NULL)
    {
      *err=0;
      printf("nil.\n");
      return NULL_ATOM;
    }

  atom it=(*cpp)->car;
  cell* temp=(*cpp)->cdr;
  *err=1;
  free(*cpp);
  *cpp=temp;
  return it;
}

void print_atom(atom val)
{
  printf("%d",val);
}

void print_list(cell* cp)
{
  cell* temp=cp;
  printf("[");
  while(temp!=NULL)
    {
      printf(" ");
      print_atom(temp->car);
      temp=temp->cdr;
    }
  printf(" ]\n");
}


Measured memory_bytes: 1148