#include <bits/stdc++.h>
using namespace std;
vector<int>al;
struct fa{vector<int>kim;};
bool has1(int n, int m){
    return al[n]<al[m];}
int main()
{
    //ifstream f("szamok.txt");
    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);
    for(int i=1; i<n; 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);}
    al[1]=n-1;
    for(int i:indul){
        int t=i;
        while(t!=1){
            al[t]++;
            t=apa[t];}}
    /*for(int i=1; i<=n; i++){
        cout<<i<<" "<<al[i]<<endl;}*/
    vector<int>sor;
    for(int i=2; i<=n; i++)sor.push_back(i);
    sort(sor.begin(), sor.end(), has1);
    //for(int i:sor)cout<<al[i]<<" ";
    //cout<<endl;
    //for(int i:ert)cout<<i<<" ";
    //cout<<endl;
    int s=0;
    int c=32609;
    for(int i=1; i<=n-1; i++)
        /*s+=ert[i]*al[sor[i]]*/
        s+=(ert[i]*al[sor[i-1]]*(n-al[sor[i-1]]))%c;
    cout<<2*s<<endl;
    for(int i=1; i<n; i++){
        cout<<sor[i-1]<<" "<<apa[sor[i-1]]<<" "<<ert[i]<<endl;
    }
    return 0;
}