#include <bits/stdc++.h>

using ll = long long;
using namespace std;

const int MAXN = 50'001;
const int MOD = 32609;

struct Edge {
    ll w, u, v;

    Edge(int a, int b, int c) : w(a), u(b), v(c) {}
};

vector<int> g[MAXN];
ll s[MAXN], p[MAXN];

void dfs(int u) {
    s[u] = 1;
    for (int v : g[u]) {
        if (p[u] != v) {
            p[v] = u;
            dfs(v);
            s[u] += s[v];
        }
    }
}

void solve() {
    int n; cin >> n;
    for (int i = 0; i < n-1; i++) {
        int u, v; cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector<ll> cost(n-1);
    for (ll &i : cost) cin >> i;
    dfs(1);
    vector<Edge> edges;
    for (int i = 2; i <= n; i++) {
        edges.emplace_back(s[i]*(n-s[i]), i, p[i]);
    }
    sort(cost.begin(), cost.end());
    sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b){
        return a.w < b.w;
    });
    ll ans = 0;
    for (int i = 0; i < n-1; i++) {
        ans += 2ll*edges[i].w*cost[i];
        ans %= MOD;
    }
    cout << ans << "\n";
    for (int i = 0; i < n-1; i++) {
        cout << edges[i].u << " " << edges[i].v << " " << cost[i] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}