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

long long n, MOD = 32609;
vector<long long> gyersz;
vector<vector<long long>> fiu;
vector<pair<long long, pair<long long, long long>>> el;

long long gyerek(long long k) {
    gyersz[k] += fiu[k].size();
    for(auto i : fiu[k]) gyersz[k] += gyerek(i);
    return gyersz[k];
}

int main() {
    cin >> n;
    fiu.resize(n+1, vector<long long>(0)); gyersz.resize(n+1, 0); el.resize(n-1);
    for(long long i = 0; i < n-1; i++) {
        long long a, b;
        cin >> a >> b;
        fiu[a].push_back(b);
        el[i].second.first = a;
        el[i].second.second = b;
    }

    gyerek(1);
    for(long long i = 0; i < n-1; i++) {
        el[i].first = 2*(1+gyersz[el[i].second.second])*(n-(1+gyersz[el[i].second.second])) % MOD;
    }
    sort(el.begin(), el.end());

    vector<long long> hosszak(n-1);
    for(long long i = 0; i < n-1; i++) {
        cin >> hosszak[i];
    }
    sort(hosszak.begin(), hosszak.end());

    long long s = 0;
    for(long long i = 0; i < n-1; i++) {
        hosszak[i] %= MOD;
        s = (s + hosszak[i]*el[i].first % MOD) % MOD;
    }

    cout << s << '\n';
    for(long long i = 0; i < n-1; i++) {
        cout << el[i].second.first << ' ' << el[i].second.second << ' ' << hosszak[i] << '\n';
    }

	return 0;
}