#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

ll mod=32609;
ll n;
vector<ll>vis;
vector<vector<ll>>g;
vector<ll>child;
vector<ll>row;
vector<ll>ado;
vector<bool>kifok;
vector<pair<ll,pair<ll,ll>>>elek;


void dfs(ll v)
{
    vis[v]=true;
    for(ll x:g[v])
    {
        if(!vis[x])
        {
            dfs(x);
        }
    }
    row.push_back(v);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    vis.resize(n+1,0);
    g.resize(n+1);
    child.resize(n+1,0);
    ado.resize(n-1);
    kifok.resize(n+1,0);
    for(ll i=1;i<=n-1;i++)
    {
        ll a,b;
        cin>>a>>b;
        g[a].push_back(b);
        kifok[a]=true;
        elek.push_back({0,{a,b}});
    }
    for(ll i=0;i<=n-2;i++)
    {
        cin>>ado[i];
    }
    sort(ado.begin(),ado.end());
    dfs(1);
    for(ll x:row)
    {
        if(!kifok[x])
        {
            child[x]=1;
        }else
        {
            for(ll y:g[x])
            {
                child[x]+=child[y];
            }
            child[x]+=1;
        }
    }
    for(auto &x:elek)
    {
        x.first=child[x.second.second]*(n-child[x.second.second]);
    }
    sort(elek.begin(),elek.end());
    ll sum=0;
    for(ll i=0;i<=n-2;i++)
    {
        sum+=ado[i]*elek[i].first;
        sum%=mod;
        elek[i].first=ado[i];
    }
    sum*=2;
    sum%=mod;
    cout<<sum<<'\n';
    for(auto x:elek)
    {
        cout<<x.second.first<<" "<<x.second.second<<" "<<x.first<<'\n';
    }
    return 0;
}