// 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> depth,siz;

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

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

signed main() {
    cin>>n;
    vector<pair<int,int>> elek;
    vector<vector<int>> v(n);
    depth.resize(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, 0);
    sort(elek.begin(),elek.end(),hasonlo);
    int ans=0;
    for(int i = 0;i<n-1;i++){
        int temp=siz[elek[i].second];
        ans+=(temp*(n-temp)*arak[i]*2)%32609;
    }cout<<ans<<endl;
    for(int i = 0;i<n-1;i++){
        cout<<elek[i].first+1<<' '<<elek[i].second+1<<' '<<arak[i]<<endl;
    }
}