#include <bits/stdc++.h>
using namespace std;
vector<int>al;
struct fa{vector<int>kim;};
struct ut{int apa, fia, hany, ert;};
bool has1(ut n, ut m){
    return n.hany<m.hany;}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin>>n; vector<fa>a(n+1); vector<int>apa(n+1);
    al.resize(n+1);
    vector<bool>volt(n+1),joe(n+1); volt[1]=1;
    for(int i=1; i<n; i++){
        int x,y; cin>>x>>y;
        a[x].kim.push_back(y);
        a[y].kim.push_back(x);}
    vector<int>ert(n-1);
    for(int i=0; i<n-1; i++)cin>>ert[i];
    sort(ert.begin(), ert.end());
    queue<int>q; q.push(1);
    while(!q.empty()){
        int r=q.front();
        for(int i:a[r].kim){
            if(!volt[i]){
                apa[i]=r;
                volt[i]=1;
                q.push(i);}}
        q.pop();}
    for(int i=1; i<=n; i++){
        joe[apa[i]]=1;}
    vector<int>indul;
     for(int i=1; i<=n; i++){
        if(!joe[i])indul.push_back(i);}
    vector<bool>van(n+1); van[1]=1; al[1]=1;
    for(int i:indul){
        int t=i,k=1;
        while(!van[t]){
            al[t]+=k;
            van[t]=1;
            k++; t=apa[t];}
        while(t!=1){
            al[t]+=k-1; t=apa[t];}
        al[1]+=k-1;}
    vector<ut>b(n-1);
    for(int i=0; i<n-1; i++){
        b[i].fia=i+2; b[i].apa=apa[i+2];
        b[i].hany=al[i+2]*(n-al[i+2]);}
    sort(b.begin(), b.end(), has1);
    for(int i=0; i<n-1; i++)b[i].ert=ert[i];
    int c=32609; long long s=0;
    for(int i=0; i<n-1; i++){
        s+=2*(ert[i]%c)*(b[i].hany%c);
        s%=c;}
    cout<<s<<endl;
    for(ut i:b)cout<<i.apa<<" "<<i.fia<<" "<<i.ert<<endl;
    return 0;
}