// Útadó jo.cpp : his file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dfs(int v, int parent, 
    vector<vector<int>>& adj,
    vector<int> &under)
{
    under[v] = 1;
    for (auto to : adj[v])
    {
        if (to == parent)
            continue;
        under[v]+=dfs(to, v, adj,under);
    }
    return under[v];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; 
    cin >> n;
    long long sum = 0;
    vector<vector<int>> adj(n + 1);
    //2. edge id
    vector<pair<int,int>> edge;
    vector<int> under(n+1);
    for (int i = 1; i <= n-1; i++)
    {
        int a, b;
        cin >> a >> b;
        edge.push_back({ a,b });
        adj[a].push_back(b);
    }
    vector<int> weight(n - 1);
    for (int i = 0; i < n - 1; i++)
    {
        cin >> weight[i];
    }
    sort(weight.begin(), weight.end());

    dfs(1, -1, adj, under);
    vector<pair<long long,long long>> count(n - 1);
    for (int i = 0; i < n-1; i++)
    {
        count[i] = { under[edge[i].second] * (n - under[edge[i].second]) * 2 ,i} ;
    }
    sort(count.begin(), count.end());
    for (int i = 0; i < n - 1; i++)
    {
        sum += (count[i].first * weight[i]) % 32609;
    }
    cout << sum%32609 << endl;
    for (int i = 0; i < n - 1; i++)
    {
        int x = count[i].second;
        cout << edge[x].first << " " << edge[x].second << " " << weight[i] << endl;
    }
}