#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const int mod=32609;

using namespace std;

struct csucs{
    vector<int> gyerek;
    int alatta=1, szulo, bejart=0, megvan=0;
};
struct ut{
    long long atjaras, p1, p2;
};
bool alma(ut x1, ut x2){
    return x1.atjaras<x2.atjaras;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, x, y;
    cin >> n;
    csucs a[n];
    a[0].szulo=-1;
    for(int i=1; i<n; i++){
        cin >> x >> y;
        x--;
        y--;
        a[x].gyerek.push_back(y);
        a[y].szulo=x;
    }
    queue<int> q;
    for(int i=0; i<n; i++){
        if(a[i].gyerek.size()==0){
            q.push(i);
            a[i].bejart=1;
        }
    }
    while(!q.empty()){
        x=q.front();
        q.pop();
        y=a[x].szulo;
        a[y].alatta+=a[x].alatta;
        a[y].megvan++;
        if(a[y].megvan==a[y].gyerek.size()){
            q.push(y);
        }
    }
    long long ar[n-1];
    ut b[n-1];

    for(int i=1; i<n; i++){
        b[i-1].atjaras=a[i].alatta*(n-a[i].alatta)*2;
        b[i-1].p1=i;
        b[i-1].p2=a[i].szulo;
        //cout << i+1 << ": " << b[i-1].atjaras << '\n';
        cin >> ar[i-1];
    }
    sort(b, b+n-1, alma);
    sort(ar, ar+n-1);
    long long profit=0;
    for(int i=0; i<n-1; i++){
        profit+=(ar[i]%mod)*(b[i].atjaras%mod);
        profit=profit%mod;
    }
    cout << profit << '\n';
    for(int i=0; i<n-1; i++){
        cout << b[i].p1+1 << ' ' << b[i].p2+1 << ' ' << ar[i] << '\n';
    }
    return 0;
}