// 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;
};
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;
	unordered_set<int>s;
	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++;
		if (varosok[y.cel].elszam > 1)
		{
			s.insert(y.cel);
		}
		if (varosok[x.cel].elszam > 1)
		{
			s.insert(x.cel);
		}
	}
	priority_queue<int>sulyok;
	long long suly;
	for (int i = 0; i < N - 1; i++)
	{
		cin >> suly;
		sulyok.push(suly);
	}
	vector<eredmeny>utak(N-1);
	int e = 0;
	while (s.size() > 0)
	{
		int i = 0;
		for (int id:s)
		{
			i = id;
			break;
		}
		for (int j = 0; j < varosok[i].szomszedok.size(); j++)
		{
			int akt = varosok[i].szomszedok[j].cel;
			if (varosok[akt].elszam == 1)
			{
				for (int 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)
				{
					s.erase(i);
				}
				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);
	int sum = 0;
	for (int i = 0; i < N-1; i++)
	{
		utak[i].ar = sulyok.top();
		sum += sulyok.top() * utak[i].atmegy;
		sulyok.pop();
	}
	cout << sum << endl;
	for (int 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