#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long


ll N;
ll be1, be2;
vector<ll> ellista[50005];
int fel[50005];
vector<ll> adok;

struct adat
{
    int cs;
    ll alatta=0;
    ll suly=0;
    ll felette=0;

};
bool Rend(adat a, adat b)
{
    return (a.alatta*a.felette>b.alatta*b.felette);
}
adat al[50005];

ll Mely(int cs)
{
    ll akt=1;
    for(int a:ellista[cs])
    {
        akt+=Mely(a);
    }
    al[cs].alatta=akt;
    al[cs].cs=cs;
    al[cs].felette = N-al[cs].alatta;
    return akt;
}

int main()
{
    cin >> N;
    for(int i = 0; i < N-1; i++)
    {
        cin >> be1 >> be2;
        ellista[be1].push_back(be2);
        fel[be2]=be1;
    }
    for(int i = 0; i < N-1; i++)
    {
        cin >> be1; adok.push_back(be1);
    }

    Mely(1);
    sort(al+1, al+N+1, Rend);
    sort(adok.begin(), adok.end(), greater<ll>());

    /*for(ll a:adok)
        cout << a << " ";
    cout << "\n";*/


    ll ert=0;
    for(int i = 1; i < N; i++)
    {
        al[i].suly = adok[i-1];
        ert += ((((al[i].alatta)*(N-al[i].alatta))%32609)*al[i].suly*2)%32609;
    }
    cout << ert%32609 << "\n";

    for(int i = 1; i <= N-1; i++)
    {
        cout << fel[al[i].cs] << " " << al[i].cs << " " << al[i].suly << "\n";
    }


    /*for(int i = 1; i <= N; i++)
    {
        cout << al[i].cs << ":" << al[i].alatta << " " << al[i].felette  << "=" << al[i].suly << "\n";
    }*/

    return 0;
}