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

#define int long long

int n;
vector<vector<int>> adj;
vector<pair<int, pair<int, int>>> elek;

int dfs(int v, int p) {
    int db = 1;
    for (int u : adj[v]) {
        if (u==p)continue;
        db += dfs(u, v);
    }
    if (db<n)elek.push_back({db*(n-db), {v, p}});
    return db;
}

signed main() {
    cin >> n;
    adj.resize(n+1);
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1, 0);
    vector<int> v(n-1);
    for (int i = 0; i < n-1; i++) {
        cin >> v[i];
    }
    sort(v.begin(),v.end());
    sort(elek.begin(),elek.end());
    int ans = 0;
    for (int i = 0; i < n-1; i++) {
        ans += (elek[i].first*v[i])%32609;
    }
    cout << (ans*2)%32609 << endl;
    for (int i = 0; i < n-1; i++) {
        cout << elek[i].second.first << ' ' << elek[i].second.second << ' ' << v[i] << '\n';
    }
}