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

#define int long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second

const int mod = 32609;

// tulkomplikalt adatszerkezet :( azt hittem kell... :)

struct edge {
    int to, subtree_size;
    edge() : to(0), subtree_size(0) {}
    edge(int to_, int subtree_size_) : to(to_), subtree_size(subtree_size_) {}
};

struct node {
    vector<edge> neighbours;
    node() {}
};

struct road {
    int product, a, b;
    bool operator < (const road & other) const {
        return product < other.product;
    }
    road(int product_, int a_, int b_) : product(product_), a(a_), b(b_) {}
};

int n;
vector<node> graph;
vector<int> weights;
vector<road> roads;

int dfs(int cur, int par) {
    int cur_subtree_size = 1;
    for(edge &nei : graph[cur].neighbours) {
        if(nei.to == par) continue;
        nei.subtree_size = dfs(nei.to, cur);
        cur_subtree_size += nei.subtree_size;
        roads.pb(road((n - nei.subtree_size) * nei.subtree_size, cur, nei.to));
    }
    return cur_subtree_size;
}

void solve() {
    cin >> n;
    weights.assign(n - 1, 0);
    graph.assign(1 + n, node());
    for(int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].neighbours.pb(edge(b, 0));
        graph[b].neighbours.pb(edge(a, 0));
    }
    for(int &x : weights) cin >> x;
    sort(weights.begin(), weights.end());
    dfs(1, 0);
    sort(roads.begin(), roads.end());
    int answer = 0;
    for(int i = 0; i < n - 1; i++) {
        answer += roads[i].product * weights[i];
        answer %= mod;
    }
    answer = (answer * 2) % mod;
    cout << answer << "\n";
    for(int i = 0; i < n - 1; i++) {
        cout << roads[i].a << " " << roads[i].b << " " << weights[i] << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}