// ConsoleApplication1.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <queue>
#include<set>
using namespace std;
struct ut {
	long long cel;
	long long ar;
};
struct varos {
	long long elszam;
	long long elotte;
	vector < ut>szomszedok;
};

int main()
{
	long long N;
	cin >> N;
	vector<varos>varosok(N + 1);
	ut x, y;
	x.ar = -1;
	y.ar = -1;
	for (int i = 0; i < N - 1; i++)
	{
		cin >> x.cel >> y.cel;
		varosok[x.cel].szomszedok.push_back(y);
		varosok[y.cel].szomszedok.push_back(x);
		varosok[x.cel].elszam++;
		varosok[y.cel].elszam++;
	}
	priority_queue<int>suly;
	long long s;
	for (int i = 0; i < N - 1; i++)
	{
		cin >> s;
		suly.push(-s);
	}
	//vector<vector<ut>>sulyozott(N+1);
	//ut u;
	long long ertek = 0;
	while (!suly.empty())
	{
		for (int i = 1; i < N + 1; i++)
		{
			if (varosok[i].elszam == 1)
			{
				s = -suly.top();
				suly.pop();
				long long j = 0;
				while (j < varosok[i].szomszedok.size() && varosok[varosok[i].szomszedok[j].cel].elszam <= 0)
				{
					j++;
				}
				long long id = 0;
				while (id< varosok[i].szomszedok.size())
				{
					if (varosok[varosok[i].szomszedok[id].cel].elszam==0)
					{
						varosok[i].elotte += varosok[varosok[i].szomszedok[id].cel].elotte;
					}
					id++;
				}
				varosok[varosok[i].szomszedok[j].cel].elszam--;
				varosok[i].elszam--;
				//u.ar = s;
				//u.cel = varosok[i].szomszedok[j];
				//sulyozott[i].push_back(u);
				varosok[i].szomszedok[j].ar = s;
				//u.cel = i;
				varosok[i].elotte ++;
				//sulyozott[varosok[i].szomszedok[j]].push_back(u);
				ertek += (varosok[i].elotte * (N - varosok[i].elotte) * 2 * s)% 32609;
			}
		}
	}
	cout << ertek << endl;
	for (int i = 1; i < N+1; i++)
	{
		for (int j = 0; j < varosok[i].szomszedok.size(); j++)
		{
			if (varosok[i].szomszedok[j].ar!=-1)
			{
				cout << i <<" "<< varosok[i].szomszedok[j].cel << " " << varosok[i].szomszedok[j].ar << endl;
			}
		}
	}
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file