// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int inf=1e9;

int power(int a,int b){
    if(b==0)return 1;
    return power(a,b-1)*a;
}
int n;
vector<int> siz;

bool hasonlo(pair<int,int> a, pair<int,int> b){
    return siz[a.second]*(n-siz[a.second])>siz[b.second]*(n-siz[b.second]);
}

void dfs(vector<vector<int>>& v, int i){
    siz[i]=1;
    for(int j : v[i]){
        dfs(v,j);
        siz[i]+=siz[j];
    }
}

signed main() {
    cin>>n;
    vector<pair<int,int>> elek;
    vector<vector<int>> v(n);
    siz.resize(n);
    for(int i = 0;i<n-1;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        elek.push_back({a,b});
        v[a].push_back(b);
    }
    vector<int> arak(n-1);
    for(int i = 0;i<n-1;i++){
        cin>>arak[i];
    }
    sort(arak.rbegin(),arak.rend());
    dfs(v, 0);
    sort(elek.begin(),elek.end(),hasonlo);
    int ans=0;
    //for(int i = 0;i<n-1;i++)cerr<<elek[i].first<<' '<<elek[i].second<<endl;
    for(int i = 0;i<n-1;i++){
        int temp=siz[elek[i].second];
        ans+=((temp*(n-temp)%32609)*(arak[i]*2)%32609);
        ans%=32609;
    }cout<<ans<<endl;
    for(int i = 0;i<n-1;i++){
        cout<<elek[i].first+1<<' '<<elek[i].second+1<<' '<<arak[i]<<endl;
    }
}