#include<bits/stdc++.h>

using namespace std;

class pont{
public:
    vector<int> hova;
    long long meret=0;
    int dfs();
};

class edge{
public:
    int a, b;
    long long meret=0;
    int resi;
};

vector<pont> p;
vector<edge> e;

int n;

int pont::dfs(){
    if(!meret){
        meret = 1;
        for(int i : hova){
            meret+=p[i].dfs();
        }
        return meret;
    }
    return 0;
}

bool cmp1(const edge& e1, const edge& e2){
    return e1.meret < e2.meret;
}

int main(){
    cin >> n;
    //cout << n << "=N\n";
    p.resize(n);
    e.resize(n-1);
    //cout << n << "=N\n";
    for(int i=0;i<n-1;i++){
        cin >> e[i].a >> e[i].b;
        --e[i].a; --e[i].b;
        p[e[i].a].hova.push_back(e[i].b);
        p[e[i].b].hova.push_back(e[i].a);
    }
    //cout << n << "=N\n";
    p[0].dfs();
    //cout << n << "=N\n";
    for(int i=0;i<n-1;i++){
        e[i].meret = min(p[e[i].a].meret,p[e[i].b].meret)*
        (n-(min(p[e[i].a].meret,p[e[i].b].meret)));
    }
    //cout << n << "=N\n";
    vector<int> v(n-1);
    for(int i=0;i<n-1;i++){
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    sort(e.begin(), e.end(), cmp1);
    long long er = 0;
    for(int i=0;i<n-1;i++){
        e[i].resi = v[i];
        er+=e[i].meret%32609*e[i].resi;
        er%=32609;
    }
    cout << er*2%32609 << '\n';
    for(int i=0;i<n-1;i++){
        cout << e[i].a+1 << ' ' << e[i].b+1 << ' ' << e[i].resi << '\n';
    }
return 0;
}