// Utado.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
struct adat
{
bool lat=0;
int ag = 1;
vector <int> sz;
};
struct adat2
{
int db=0;
pair<int, int> par;
};
struct adat3
{
int cost, poz;
pair <int, int> elek;
};
int i, n, a, b, mod=32609;
long long sum;
vector <adat> x;
void mely(int akt)
{
x[akt].lat = 1;
for (auto& e : x[akt].sz)
{
if (!x[e].lat)
{
mely(e);
x[akt].ag += x[e].ag;
}
}
}
bool comp(adat3 a, adat3 b)
{
return a.cost<b.cost;
}
bool comp2(adat2 a, adat2 b)
{
return a.db < b.db;
}
bool comp3(adat3 a, adat3 b)
{
return a.poz < b.poz;
}
int main()
{
cin >> n;
vector <adat2> el(n);
vector <adat3> ar(n);
x.resize(n + 1);
for (i = 1; i < n; ++i)
{
cin >> a >> b;
el[i].par = { a, b };
x[a].sz.push_back(b);
x[b].sz.push_back(a);
}
for (i = 1; i < n; ++i)
{
cin >> ar[i].cost;
ar[i].poz = i;
}
mely(1);
sort(ar.begin() + 1, ar.end(), comp);
for (i = 1; i < n; ++i)
{
b = el[i].par.second;
el[i].db = 2 * x[b].ag * (n - x[b].ag);
//cout << el[i].par.first << " " << el[i].par.second << " " << el[i].db << "\n";
}
sort(el.begin() + 1, el.end(), comp2);
for (i = 1; i < n; ++i)
{
sum = (sum + (el[i].db * ar[i].cost)) % mod;
ar[i].elek = { el[i].par.first, el[i].par.second };
}
sort(ar.begin() + 1, ar.end(), comp3);
cout << sum<<"\n";
for (i = 1; i < n; ++i)
{
cout << ar[i].elek.first << " " << ar[i].elek.second << " " << ar[i].cost << "\n";
}
return 0;
}
// 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