#include <stdio.h>
#include <vector>

// Úloha 26-3-4 Kladení pastí - těžší varianta (v čase O(N))
// Vstup:
//   Počet křižovatek (číslo N), křižovatky budeme dále číslovat 1..N
//   N-1 dvojic číšel (a, b) - cestiček (hran grafu) - čísla a, b jsou pořadová čísla vrcholů
//   N hodnot jednotlivých úsilí (v pořadí čísel vrcholů)
// Výstup: minimální cena, seznam pořadových čísel křižovatek s pastmi
// Příklad vstupu:
//   9
//   1 2
//   1 3
//   1 4
//   2 5
//   2 6
//   2 7
//   3 8
//   3 9
//   10 20 15 5 5 5 5 10 10
// Příklad výstupu:
//   Min. cena: 40
//   Umisti: 1
//   Umisti: 5
//   Umisti: 6
//   Umisti: 7
//   Umisti: 3
// Obrázek k přikladu: (Vrcholy jsou očíslovány po řádcích zleva doprava)
//             10___
//            /  \   \
//          20   15    5
//        / | \   | \
//      5   5  5  10 10

// Maximální počet křižovatek+1
#define MAX_N 10000

using namespace std;

int N; // Počet křižovatek
int U[MAX_N]; // Úsilí - cena křižóvatky, číslujeme od 1 do N
int p[MAX_N]; // Cena počátečního úseku s použitím i-tého vrcholu
int n[MAX_N]; // Cena počátečního úseku bez použití i-tého vrcholu
vector <int> seznam_sousedu[MAX_N]; // Pole seznamu sousedů

#define min(a,b) (((a)<(b)) ? (a) : (b))

void spocitej_cenu_podstromu(int vrchol, int odkud = -1) { // Jaký podstrom procházíme a odkud jsme do něj přišli
	p[vrchol] = U[vrchol];
	n[vrchol] = 0;
	for(int j = 0; j < seznam_sousedu[vrchol].size(); j++) {
		int i = seznam_sousedu[vrchol][j]; // V proměnné i máme vždy číslo jednoho souseda
		if (i == odkud)
			continue; // Neprocházej svého otce
		spocitej_cenu_podstromu(i, vrchol);
		p[vrchol] += min(p[i], n[i]);
		n[vrchol] += p[i];
	}
}

void umisti_pasti_podstromu(int vrchol, int odkud = -1, int vynut_umisteni_pasti = 0) {
	if (vynut_umisteni_pasti || (p[vrchol] <= n[vrchol])) {
		printf("Umisti: %i\n", vrchol);
		for(int j = 0; j < seznam_sousedu[vrchol].size(); j++) {
			int i = seznam_sousedu[vrchol][j]; // V proměnné i máme vždy číslo jednoho souseda
			if (i == odkud)
				continue; // Neprocházej svého otce
			umisti_pasti_podstromu(i, vrchol, 0); // Právě jsme umístili past, pro tu příští si můžeme vybrat
		}
	} else {
		for(int j = 0; j < seznam_sousedu[vrchol].size(); j++) {
			int i = seznam_sousedu[vrchol][j]; // V proměnné i máme vždy číslo jednoho souseda
			if (i == odkud)
				continue; // Neprocházej svého otce
			umisti_pasti_podstromu(i, vrchol, 1); // Past jsme neumístili, musíme ji nutně dát do všech synů
		}
	}
}

int main() {
	// Načtení vstupu
	scanf("%d", &N);
	for (int i=1; i<N; i++) { // Načtení cest
		int a,b;
		scanf("%d %d", &a, &b);
		seznam_sousedu[a].push_back(b); // Hrany si zapamatujeme u obou vrcholů
		seznam_sousedu[b].push_back(a);
	}
	for (int i=1; i<=N; i++) { // Načtení úsilí - cen
		scanf("%d", &(U[i]));
	}

	spocitej_cenu_podstromu(1); // Procházíme z vrcholu číslo 1

	printf("Min. cena: %i\n", min(p[1], n[1])); // Minimální úsilí potřebné k rozmístění pastí
	// Rekonstrukce řešení
	umisti_pasti_podstromu(1); // Musíme procházet ze stejného vrcholu

	return 0;
}