#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 7;
const ll INF = 2e18;

vector<int> solve(int k, vector<vector<ll>> a) {
	int n = a.size();
	vector<vector<ll>> dp(n + 1, vector<ll>(1 << k, -INF));
	dp[0][0] = 0;
	for (int i = 0; i < n; ++i) {
		dp[i + 1] = dp[i];
		for (int mask = 0; mask < (1 << k); ++mask) {
			if (dp[i][mask] == -INF) {
				continue;
			}
			for (int j = 0; j < 3; ++j) {
				if (!((mask >> j) & 1)) {
					int mask1 = mask | (1 << j);
					dp[i + 1][mask1] = max(dp[i + 1][mask1], dp[i][mask] + a[i][j]);
				}
			}
		}
	}
	vector<int> ret(k);
	int mask = (1 << k) - 1;
	for (int i = n; i > 0; --i) {
		if (dp[i][mask] == dp[i - 1][mask]) {
			continue;
		}
		for (int j = 0; j < 3; ++j) {
			if ((mask >> j) & 1) {
				int mask1 = mask - (1 << j);
				if (dp[i - 1][mask1] + a[i - 1][j] == dp[i][mask]) {
					ret[j] = i - 1;
					mask = mask1;
					break;
				}
			}
		}
	}
	return ret;
}

int n, k;
vector<int> g[N];
ll a[N];
ll dp[N][3];

void dfs(int v, int p = -1) {
	if (p != -1) {
		g[v].erase(find(g[v].begin(), g[v].end(), p));
	}
	for (int u : g[v]) {
		dfs(u, v);
	}
	ll sum = 0;
	for (int u : g[v]) {
		sum += a[u];
	}
	{
		// start in v, finish in son of v
		dp[v][0] = a[v];
		for (int u : g[v]) {
			dp[v][0] = max(dp[v][0], a[v] + dp[u][0] + sum - a[u]);
		}
	}
	{
		// start in v, finish in subtree of v
		dp[v][1] = a[v];
		for (int u : g[v]) {
			// go to u
			dp[v][1] = max(dp[v][1], a[v] + dp[u][1] + sum - a[u]);
			// go to son of u
			dp[v][1] = max(dp[v][1], a[v] + dp[u][2]);
		}
		for (int u1 : g[v]) {
			for (int u2 : g[v]) {
				if (u1 != u2) {
					// go to son of u1, return to u1, go to u2
					dp[v][1] = max(dp[v][1], a[v] + dp[u1][0] + dp[u2][1] + sum - a[u1] - a[u2]);
				}
			}
		}
	}
	{
		// start in son of v, pass through v, finish in subtree of v
		dp[v][2] = a[v];
		if (g[v].size() >= 3) {
			vector<vector<ll>> fuck(g[v].size(), vector<ll>(3));
			for (int i = 0; i < (int)g[v].size(); ++i) {
				int u = g[v][i];
				for (int j = 0; j < 3; ++j) {
					if (j == 2) {
						fuck[i][j] = dp[u][1];
					} else {
						fuck[i][j] = dp[u][0];
					}
					fuck[i][j] -= a[u];
				}
			}
			auto ret = solve(3, fuck);
			int u1 = g[v][ret[0]];
			int u2 = g[v][ret[1]];
			int u3 = g[v][ret[2]];
			ll cur = a[v];
			cur += dp[u1][0] + dp[u2][0] + dp[u3][1];
			cur += sum;
			cur -= a[u1] + a[u2] + a[u3];
			dp[v][2] = max(dp[v][2], cur);
		}
		for (int u1 : g[v]) {
			for (int u2 : g[v]) {
				if (u1 == u2) {
					continue;
				}
				ll cur = a[v];
				cur += dp[u1][0] + dp[u2][2];
				cur += sum;
				cur -= a[u1] + a[u2];
				dp[v][2] = max(dp[v][2], cur);
			}
		}	
	}
}

vector<int> findord(int v, int f) {
	if (dp[v][f] == a[v]) {
		return {v};
	}
	ll sum = 0;
	for (int u : g[v]) {
		sum += a[u];
	}
	if (f == 0) {
		for (int u : g[v]) {
			if (dp[v][0] == a[v] + dp[u][0] + sum - a[u]) {
				auto ordu = findord(u, 0);
				vector<int> ord = {v};
				reverse(ordu.begin(), ordu.end());
				ord.insert(ord.end(), ordu.begin(), ordu.end());
				for (int w : g[v]) {
					if (w != u) {
						ord.push_back(w);
					}
				}
				return ord;
			}
		}
		assert(0 && "kek");
		return {v};
	}
	if (f == 1) {
		for (int u : g[v]) {
			// go to u
			if (dp[v][1] == a[v] + dp[u][1] + sum - a[u]) {
				auto ordu = findord(u, 1);
				vector<int> ord = {v};
				for (int w : g[v]) {
					if (w != u) {
						ord.push_back(w);
					}
				}
				ord.insert(ord.end(), ordu.begin(), ordu.end());
				return ord;
			}
			// go to son of u
			if (dp[v][1] == a[v] + dp[u][2]) {
				auto ordu = findord(u, 2);
				vector<int> ord = {v};
				ord.insert(ord.end(), ordu.begin(), ordu.end());
				return ord;
			}
		}
		for (int u1 : g[v]) {
			for (int u2 : g[v]) {
				if (u1 != u2 && dp[v][1] == a[v] + dp[u1][0] + dp[u2][1] + sum - a[u1] - a[u2]) {
					auto ordu1 = findord(u1, 0);
					auto ordu2 = findord(u2, 1);
					vector<int> ord = {v};
					reverse(ordu1.begin(), ordu1.end());
					ord.insert(ord.end(), ordu1.begin(), ordu1.end());
					for (int w : g[v]) {
						if (w != u1 && w != u2) {
							ord.push_back(w);
						}
					}
					ord.insert(ord.end(), ordu2.begin(), ordu2.end());
					return ord;
				}
			}
		}
		assert(0 && "lol");
		return {v};
	}
	if (f == 2) {
		for (int u1 : g[v]) {
			for (int u2 : g[v]) {
				for (int u3 : g[v]) {
					if (u1 == u2 || u2 == u3 || u1 == u3) {
						continue;
					}
					ll cur = a[v];
					cur += dp[u1][0] + dp[u2][0] + dp[u3][1];
					cur += sum;
					cur -= a[u1] + a[u2] + a[u3];
					if (cur == dp[v][2]) {
						auto ordu1 = findord(u1, 0);
						auto ordu2 = findord(u2, 0);
						auto ordu3 = findord(u3, 1);
						vector<int> ord;
						ord.insert(ord.end(), ordu1.begin(), ordu1.end());
						ord.push_back(v);
						reverse(ordu2.begin(), ordu2.end());
						ord.insert(ord.end(), ordu2.begin(), ordu2.end());
						for (int w : g[v]) {
							if (w != u1 && w != u2 && w != u3) {
								ord.push_back(w);
							}
						}
						ord.insert(ord.end(), ordu3.begin(), ordu3.end());
						return ord;
					}
				}
			}
		}
		for (int u1 : g[v]) {
			for (int u2 : g[v]) {
				if (u1 == u2) {
					continue;
				}
				ll cur = a[v];
				cur += dp[u1][0] + dp[u2][2];
				cur += sum;
				cur -= a[u1] + a[u2];
				if (dp[v][2] == cur) {
					vector<int> ord;
					auto ordu1 = findord(u1, 0);
					auto ordu2 = findord(u2, 2);
					for (int w : g[v]) {
						if (w != u1 && w != u2) {
							ord.push_back(w);
						}
					}
					ord.insert(ord.end(), ordu1.begin(), ordu1.end());
					ord.push_back(v);
					ord.insert(ord.end(), ordu2.begin(), ordu2.end());
					return ord;
				}
			}
		}
		
		assert(0 && "rofl");
		return {v};
	}
	assert(0 && "fuck");
	return {v};
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n - 1; ++i) {
		int v, u;
		cin >> v >> u;
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	dfs(0);
	cout << dp[0][1] << "\n";
	auto ord = findord(0, 1);
	cout << ord.size() << "\n";
	for (int v : ord) {
		cout << v + 1 << " ";
	}
	cout << "\n";
	return 0;	
}