#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct cuc
{
    ll el=0, cur, su;
};
bool f(cuc a, cuc b)
{
    return a.su>b.su;
}
int main()
{
    //ifstream cin("f.txt");
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n, a, b, i, cica=0;
    cin >> n;
    ll apa[n+1]={0};
    cuc sum[n+1];
    ll alul[n+1]={};
    ll num[n+1]={};
    for(i=1; i<n; i++)
    {
        cin >> a >> b;
        apa[b]=a;
        num[a]++;
        sum[b].el=a;
        sum[b].cur=b;
    }
    queue<ll>q;
    for(i=1; i<=n; i++)
    {
        alul[i]=1;
        if(!num[i])q.push(i);
    }
    while(!q.empty() && q.front()!=1)
    {
        a=q.front();
        q.pop();
        num[apa[a]]--;
        sum[a].su=2*alul[a]*(n-alul[a]);
        alul[apa[a]]+=alul[a];
        if(num[apa[a]]==0)q.push(apa[a]);
    }
    sort(sum+2, sum+n+1, f);
    ll values[n];
    for(i=1; i<n; i++)cin >> values[i];
    sort(values+1, values+n, greater<ll>());
    for(i=1; i<n; i++)cica=(cica+values[i]*sum[i+1].su)%32609;
    cout << cica << endl;
    for(i=2; i<=n; i++)cout << sum[i].el << " " << sum[i].cur << " " << values[i-1] << endl;
    return 0;
}