#include <bits/stdc++.h>
using namespace std;
using ll=long long;
vector<ll> g[50001];
vector<ll>c(50001);
vector<pair<ll,int>> db ; 
ll dfs(int x){
	if (c[x]==0){
		db[x]={1,x};
		return db[x].first;
	} 
	else{
		for (int edge:g[x]){
			db[x].first+=dfs(edge);
			db[x].second=x; 
		}
	}
	return (db[x].first);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;

vector<int> p;
p.resize(n+1);
for (int i=1;i<n;i++)
{
ll x,y;
cin>>x>>y;
db.assign(n+1, {1,0}); 
c[x]++; 
p[y]=x;
g[x].push_back(y);

}
vector<ll> arak;
for (int i=1; i<n;i++){
	ll x;
	cin>>x; 
	x=x%32609;
	arak.push_back(x);
}

dfs(1);
for (int i=1; i<=n;i++) db[i].first=db[i].first*(n-db[i].first)%32609;
sort(db.begin(), db.end());
sort(arak.begin(), arak.end());
ll ans=0; 
vector<pair<pair<ll, ll>,ll>> cnt; 
for (int i=2; i<=n;i++){
	ans+=db[i].first*arak[i-2]*2;
	ans=ans%32609;
	cnt.push_back({{db[i].second, p[db[i].second]},arak[i-2]});
}
cout<<ans<<endl; 
for (auto x: cnt) cout<<x.first.second<<" "<<x.first.first<<" "<<x.second<<endl; 

}