#include <iostream>
#include <algorithm> // for sort, mainly
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <array>
#include <string>
#include <cstdio>
#include <iterator>
#include <unordered_set>
#include <cstdint> // for int64_t, int32_t, etc
#include <queue>
#include <stack>
#include <deque>
#include <numeric> // gcd, lcm
#include <fstream>
#include <bitset> // for bitset
#include <iomanip>
#include <cassert> // for set with custom ordering
#include <type_traits> // for set with custom ordering
#include <utility> // for swap, forward, etc
using namespace std;

#pragma GCC optimize("O2")
// #pragma GCC optimize("O1","O2","O3","Ofast","unroll-loops")
// #pragma GCC target("sse","sse2","sse3","sse4.1","sse4.2","avx","avx2","fma")

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

/*

notes:

int64_t
stoi(string s) -> string to int
to_string() -> int (or else) to string

vector declaration:
vector<ll> v(n, 0)
vector<vector<ll>> v(n, vector<ll>(n, 0));

{if statement} ? {truth value} : {false value}

#ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif

std::lcm(ll a, ll b), std::gcd(int a, int b)

cout << fixed << setprecision(n);

set with custom ordering
set<ll, decltype(&cmp)> qu(cmp);

*/

typedef int64_t ll;

const ll md = 32609;

void solve() {

	// szortirozzuk az adokat
	// minden utra kiszamoljuk, hanyszor van hasznalva

	ll n;
	cin >> n;

	vector<vector<ll>> ch(n+1);
	vector<ll> p(n+1, -1);
	vector<ll> in(n+1, 0);

	vector<bool> leaf(n+1, true);

	for(ll i = 0; i < n - 1; i++) {
		ll a, b;
		cin >> a >> b;
		ch[a].push_back(b);
		p[b] = a;
		in[a]++;
		leaf[a] = false;
	}

	vector<ll> weights(n-1, 0);
	for(ll i = 0; i < n-1; i++) {
		cin >> weights[i];
	}

	sort(weights.rbegin(), weights.rend());

	// for each node, we calculate the size of its subtree
	// then we do a bfs from each node
	// and in the bfs, we manually calculate how many times are each road used in this specific instance

	vector<ll> sub(n+1, 0); // size of subtree
	queue<ll> subcount;
	for(ll i = 1; i <= n; i++) {
		if(leaf[i]) {
			subcount.push(i);
		}
	}
	while(!subcount.empty()) {

		ll curr = subcount.front();
		subcount.pop();

		sub[curr]++;
		if(curr == 1) {
			break;
		}
		sub[p[curr]] += sub[curr];

		in[p[curr]]--;
		if(in[p[curr]] == 0) {
			subcount.push(p[curr]);
		}
	}

	//cerr << "\nsub=" << sub;

	vector<ll> u(n+1, 0); // used: path from [node] to p[node]
	
	/*
	for(ll i = 1; i <= n; i++) {

		// when starting from the node, nobody leaves behind to examine it
		// in the following, it will be important

		// how many go towards the parent?
		// tree size - subtree size of current node
		// (make sure not to visit already visited nodes, don't forget)

		//cerr << "\ni=" << i;

		vector<bool> vis(n+1, false);
		queue<pair<ll,ll>> q; // node, number of "tourists"
		q.push({i, n-1});
		while(!q.empty()) {

			auto c = q.front();
			q.pop();

			ll curr = c.first;
			vis[curr] = true;
			ll num = c.second;

			if(curr != i) {
				num--;
			}

			if(p[curr] != -1 && vis[p[curr]] == false) {
				vis[p[curr]] = true;
				ll h = n - 1 - (sub[curr] - 1);
				q.push({p[curr], h});
				u[curr] += h;
				//u[curr] %= md;
			}

			for(const auto & child : ch[curr]) {
				
				if(vis[child] == false) {
					vis[child] = true;
					q.push({child, sub[child]});
					u[child] += sub[child];
					//u[child] %= md;
				}
			}
		}

		//cerr << "\nu=" << u;
	}

	cerr << "\nu=" << u;
	*/

	// I'm reasonably certain we can find a pattern
	// some multiplication of parent/child that would give the amount of times a path is used
	for(ll i = 2; i <= n; i++) {

		//cerr << "\ncurrent=" << i;
		//cerr << "\npath to parent is used " << u[i];
		//cerr << "\ntree except current subtree " << n - sub[i];
		//cerr << "\nsubtree " << sub[i];

		u[i] = (n - sub[i]) * sub[i] * 2;
	}

	vector<pair<ll,ll>> fin;
	for(ll i = 2; i <= n; i++) {
		fin.push_back({u[i], i});
	}

	ll ansc = 0;

	sort(fin.rbegin(), fin.rend());
	for(ll i = 0; i < n-1; i++) {

		ansc += fin[i].first * weights[i];
		ansc %= md;
	}

	//cerr << "\nfin=" << fin;

	//cerr << "\nansc=" << ansc;

	cout << ansc << "\n";
	for(ll i = 0; i < n-1; i++) {
		
		ll h = fin[i].second;

		cout << p[h] << " " << h << " " << weights[i] << "\n";
	}
}

int main()
{
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	solve();

	return 0;
}