#include <bits/stdc++.h>

#pragma region Utility

#define speed cin.tie(0); ios::sync_with_stdio(0)
#define cinv(v) for (auto& e : v) cin >> e;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define size(v) (int)v.size()
#define has(s, e) s.count(e)

#define max_index(v) max_element(all(v)) - v.begin()
#define min_index(v) min_element(all(v)) - v.begin()
#define smax(x, y) x = max(x, y)
#define smin(x, y) x = min(x, y)

#define sum(v) accumulate(all(v), 0)
#define product(v, T) accumulate(all(v), 1, multiplies<T>())

using namespace std;
using ll = long long;
using point = array<int, 2>;

int max(point p) { return max(p[0], p[1]); }
int min(point p) { return min(p[0], p[1]); }

template <typename T>
vector<T> prefix_sum(const vector<T>& v) {
    vector<T> result(size(v));
    partial_sum(all(v), result.begin());
    return result;
}

#pragma endregion

const int MOD = 32609;

int N;
vector<vector<int>> g;
vector<vector<bool>> gm;
vector<int> trafficS;
vector<bool> vis;
priority_queue<int> weightS;

int dfs(int s, int p) {
    if (s == p || vis[s]) return 0;
    vis[s] = 1;

    int result = 1;
    for (int e : g[s]) {
        result += dfs(e, p);
    }

    //cout << s << ' ';

    return result;
}

void traverse(int s) {
    //cout << "S = " << s << " | ";
    if (size(g[s]) == 0) {
        trafficS[s] = N - 1;
        //cout << trafficS[s] << '\n';
        return;
    }

    vis.assign(N + 1, 0);

    int up = dfs(1, s), down = N - up;

    trafficS[s] = up * down * 2;
    //cout << "| " << trafficS[s] << '\n';
}

struct Edge {
public:
    int from;
    int to;
    int traffic;
    bool operator()(const Edge& a, const Edge& b) {
        return a.traffic < b.traffic;
    }
};

int parent(int s) {
    for (int i = 0; i < size(g[s]); i++) {
        if (gm[s][i]) {
            return g[s][i];
        }
    }
    return 0;
}

int main() {
    speed;

    cin >> N;

    g.resize(N + 1);
    gm.resize(N + 1);
    
    for (int i = 1; i < N; i++) {
        int U, V;
        cin >> U >> V;
        g[U].push_back(V);
        gm[U].push_back(0);

        g[V].push_back(U);
        gm[V].push_back(1);
    }

    for (int i = 1; i < N; i++) {
        int W;
        cin >> W;
        weightS.push(W);
    }

    trafficS.assign(N + 1, -1);

    for (int i = 2; i <= N; i++) {
        traverse(i);
    }


    //cout << '\n';
    //for (int x : trafficS) cout << x << ' ';
    //cout << endl;

    priority_queue<Edge, vector<Edge>, Edge> edgeS;

    for (int i = 2; i <= N; i++) {
        edgeS.push({parent(i), i, trafficS[i]});
    }

    // cout << size(edgeS) << ' ' << size(weightS) << '\n';

    int result = 0;
    vector<array<int, 3>> mappingS;

    // cout << '\n';

    while (!weightS.empty()) {
        int w = weightS.top();
        weightS.pop();
        Edge e = edgeS.top();
        edgeS.pop();

        mappingS.push_back({e.from, e.to, w});
        result += w * e.traffic;
        result %= MOD;

        // cout << e.from << ' ' << e.to << ' ' << w * e.traffic << '\n';
    }

    cout << result << '\n'; // can go both ways
    for (const auto& mapping : mappingS) {
        cout << mapping[0] << ' ' << mapping[1] << ' ' << mapping[2] << '\n';
    }
}