// 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