#include <iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>

using namespace std;

int const d=32609;

long long int n,a,b;
long long int s=0;
vector<long long int>edges;
vector<vector<pair<int,int> > > g;
vector<long long int>labels;
vector<long long int>dp;
priority_queue<pair<long long int,int> > seged;
vector<pair<int,int> > lo;

void dfs(int node)
{
    for(auto to:g[node])
    {
        dfs(to.first);
        dp[node]+=dp[to.first];
        seged.push(make_pair(dp[to.first]*(n-dp[to.first])*2,to.second));
    }
}

int main()
{
    cin>>n;
    g.resize(n+1);
    labels.resize(n-1);
    edges.resize(n);
    dp.assign(n+1,1);
    lo.resize(n+1);
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        g[a].push_back(make_pair(b,i));
        lo[i]=make_pair(b,a);
    }
    for(int i=0;i<n-1;i++) cin>>labels[i];
    sort(labels.begin(),labels.end(),greater<>());
    dfs(1);
    a=0;
    while(!seged.empty())
    {
        s+=labels[a]*seged.top().first;
        s%=d;
        edges[seged.top().second]=labels[a];
        ++a;
        seged.pop();
    }
    cout<<s<<endl;
    for(int i=1;i<=n-1;i++)
    {
        cout<<lo[i].first<<" "<<lo[i].second<<" "<<edges[i]<<"\n";
    }
    return 0;
}