#include <bits/stdc++.h>

using namespace std;


typedef long long ll;
typedef pair<ll, ll> pii;

const ll MOD = 32609;

vector<vector<ll>> csucsok;
vector<ll> alatta;

ll bejar(ll akt, ll elozo){
    for(ll x : csucsok[akt]){
        if(x == elozo) continue;

        alatta[akt] += bejar(x, akt);
    }

    alatta[akt]++;
    return alatta[akt];
}

int main()
{
    ll n;
    cin >> n;

    ll m = n - 1;

    csucsok.assign(n, vector<ll>());
    vector<pii> elek;
    for(ll i = 0; i < m; i++){
        ll a, b;
        cin >> a >> b;
        a--; b--;

        csucsok[a].push_back(b);
        csucsok[b].push_back(a);
        elek.push_back({a, b});
    }

    alatta.assign(n, 0);
    bejar(0, -1);

    vector<ll> adok(m);
    for(ll i = 0; i < m; i++){
        cin >> adok[i];
    }

    sort(adok.begin(), adok.end(), greater<ll>());

    vector<pii> sor(m);
    for(ll i = 0; i < m; i++){
        ll a = alatta[elek[i].first];
        ll b = alatta[elek[i].second];

        ll lent, fent;

        if(a < b){
            lent = a;
            fent = n - a;
        } else{
            lent = b;
            fent = n - b;
        }

        sor[i] = {lent * fent, i};
    }

    ll valasz = 0;

    sort(sor.begin(), sor.end(), greater<pii>());
    for(ll i = 0; i < m; i++){
        valasz += sor[i].first * adok[i];
        valasz %= MOD;
    }

    cout << (valasz * 2) % MOD << "\n";

    for(ll i = 0; i < m; i++){
        cout << elek[sor[i].second].first + 1 << " " << elek[sor[i].second].second + 1 << " " << adok[i] << "\n";
    }
}