// 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 (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)
{
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<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;
int s = 0;
while (e<N-1)
{
for (int i = 0; i < N; i++)
{
if (!varosok[i].volt)
{
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)
{
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);
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