#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;
//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 * 2 << '\n'; // can go both ways
for (const auto& mapping : mappingS) {
cout << mapping[0] << ' ' << mapping[1] << ' ' << mapping[2] << '\n';
}
}