#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 32609;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<array<int,2>> child(n+1, {0,0});
    vector<int> deg(n+1, 0);
    vector<int> parent(n+1, 0);

    vector<pair<int,int>> edge(n); // 1..n-1
    for (int i = 1; i <= n-1; i++) {
        int a,b;
        cin >> a >> b;           // a parent, b child
        edge[i] = {a,b};
        parent[b] = a;
        child[a][deg[a]++] = b;  // 0 or 1 (binary)
    }

    vector<long long> w(n);      // 1..n-1
    for (int i = 1; i <= n-1; i++) cin >> w[i];
    sort(w.begin()+1, w.begin()+n); // ascending (ok)

    // subtree sizes via reverse order (no recursion)
    vector<int> under(n+1, 1);
    for (int v = n; v >= 2; v--) {   // nodes 2..n have a parent
        under[parent[v]] += under[v];
    }

    vector<pair<long long,int>> coef(n); // 1..n-1: (coef, edgeIndex)
    for (int i = 1; i <= n-1; i++) {
        int b = edge[i].second;
        long long s = under[b];
        long long c = 2LL * s * (n - s);
        coef[i] = {c, i};
    }
    sort(coef.begin()+1, coef.begin()+n); // ascending

    long long ans = 0;
    for (int i = 1; i <= n-1; i++) {
        ans = (ans + (coef[i].first % MOD) * (w[i] % MOD)) % MOD;
    }

    cout << ans << "\n";
    for (int i = 1; i <= n-1; i++) {
        int ei = coef[i].second; // which edge gets w[i]
        cout << edge[ei].first << " " << edge[ei].second << " " << w[i] << "\n";
    }
}