#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
vector<vector<int>> adj;
int n;
vector<bool> vis;
vector<int> subsize;
vector<tuple<int,int,int>> ans;

void subsizecalc(int s)
{
vis[s]=true;
for(auto x:adj[s])
    {
    if(!vis[x])
        {
        subsizecalc(x);
        subsize[s]+=subsize[x];

        }
    }
}
int timer=0;
void anscalc(int s)
{
vis[s]=true;
for(int x:adj[s])
    {
    if(!vis[x])
        {
        ans.push_back({s,x,(n-subsize[x])*subsize[x]*2});
        anscalc(x);
        }
    }
}

int main()
{
    cin>>n;
    adj.resize(n+1);
    vis.resize(n+1,false);
    subsize.resize(n+1,1);
    int x,y;
    ans.reserve(n+1);
    for(int i=0;i<n-1;i++)
        {
        cin>>x>>y;
        adj[y].push_back(x);
        adj[x].push_back(y);
        }
    subsizecalc(1);
    fill(vis.begin(), vis.end(), false);
    anscalc(1);
    //cout<<ans.size()<<" \n";
    vector<int> w(n-1);
    for(int &x:w)cin>>x;
    sort(w.begin(),w.end(),greater<int>());
    sort(ans.begin(),ans.end(),[](tuple<int,int,int> a,tuple<int,int,int> b)
         {
         return get<2>(a)>get<2>(b);
         });
    long long sum=0;
    for(int i=0;i<n-1;i++)
        {
        sum=(sum+(w[i]*1LL)*(get<2>(ans[i])*1LL))%32609;
        }
    cout<<sum<<"\n";
    for(int i=0;i<n-1;i++)
        {
        cout<<get<0>(ans[i])<<" "<<get<1>(ans[i])<<" "<<w[i]<<"\n";
        }
    return 0;
}