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

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

using namespace std;

struct ut {
	long long elotte;
	long long cel;
};
struct varos {
	long long elszam;
	vector <ut>szomszedok;
	bool volt;
};
struct eredmeny {
	long long atmegy;
	long long kezd;
	long long veg;
	long long ar;
};
bool rendez(eredmeny e1, eredmeny e2) {
	return e1.atmegy > e2.atmegy;
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	long long N;
	cin >> N;
	vector<varos>varosok(N + 1);
	ut x, y;
	x.elotte = 0;
	y.elotte = 0;
	for (long long 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++;
		if (varosok[y.cel].elszam > 1)
		{
			varosok[y.cel].volt = false;
		}
		else
		{
			varosok[y.cel].volt = true;
		}
		if (varosok[x.cel].elszam > 1)
		{
			varosok[x.cel].volt = false;
		}
		else
		{
			varosok[x.cel].volt = true;
		}
	}
	priority_queue<long long>sulyok;
	long long suly;
	for (long long i = 0; i < N - 1; i++)
	{
		cin >> suly;
		sulyok.push(suly);
	}
	vector<eredmeny>utak(N - 1);
	long long e = 0;
	long long s = 0;
	while (e<N-1)
	{
		for (long long i = 0; i < N; i++)
		{
			if (!varosok[i].volt)
			{
				for (long long j = 0; j < varosok[i].szomszedok.size(); j++)
				{
					long long akt = varosok[i].szomszedok[j].cel;
					if (varosok[akt].elszam == 1)
					{
						for (long long k = 0; k < varosok[akt].szomszedok.size(); k++)
						{
							if (varosok[akt].szomszedok[k].cel != i)
							{
								varosok[i].szomszedok[j].elotte += varosok[akt].szomszedok[k].elotte;
							}
						}
						varosok[i].szomszedok[j].elotte++;
						varosok[akt].elszam = 0;
						varosok[i].elszam--;
						if (varosok[i].elszam == 1)
						{
							varosok[i].volt = true;
						}
						utak[e].kezd = i;
						utak[e].veg = akt;
						utak[e].atmegy = varosok[i].szomszedok[j].elotte * (N - varosok[i].szomszedok[j].elotte) * 2;
						e++;
					}
				}
			}
			
		}


	}
	sort(utak.begin(), utak.end(), rendez);
	long long sum = 0;
	for (long long i = 0; i < N - 1; i++)
	{
		utak[i].ar = sulyok.top();
		sum += (sulyok.top() * utak[i].atmegy)% 32609;
		sulyok.pop();
	}
	cout << sum << endl;
	for (long long i = 0; i < N - 1; i++)
	{
		cout << utak[i].kezd << " " << utak[i].veg << " " << utak[i].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