#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll MOD = 32609;
#define fi first
#define se second
vector<vector<int> > g;
vector<int> p;
vector<pair<ll, int> > times;
ll n;

ll mul(ll a, ll b){
    a %= MOD;
    b %= MOD;
    return a * b % MOD;
}

int dfs(int v){
    ll r = 1;
    for (int x : g[v]){
        if (x == p[v]) continue;
        p[x] = v;
        r += dfs(x);
    }
    times[v].se = v;
    times[v].fi = r * 2 * (n - r);
    return r;
}

int main()
{
    cin >> n;
    g.resize(n+1);
    p.resize(n+1);
    times.resize(n+1);
    for (int i=0; i<n-1; i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    p[1] = 0;
    dfs(1);
    vector<ll> w(n+1, 0);
    for (int i=2; i<=n; i++){
        cin >> w[i];
    }
    sort(w.begin(), w.end());
    sort(times.begin(), times.end());
    ll op = 0;
    for (int i=2; i<=n; i++){
        op += mul(w[i], times[i].fi);
    }
    cout << op << "\n";
    for (int i=2; i<=n; i++){
        cout << times[i].se << " " << p[times[i].se] << " " << w[i] << "\n";
    }
}