#include <fstream>
#include <vector>
using namespace std;
ifstream cin ("harbingers.in");
ofstream cout ("harbingers.out");
struct Dreapta {
int64_t panta = 0 , termen = 1000000000000000000LL;
Dreapta *stanga = NULL , *dreapta = NULL;
int64_t operator ()(int64_t punct) { return panta * punct + termen; }
};
Dreapta *radacina[100001];
vector < pair <int , int> > adiacenta[100001];
int termen[100001] , factor[100001] , adancime[100001];
int64_t minim[100001];
inline void Update (Dreapta* &anterior , Dreapta* &actual , const int stanga , const int dreapta , Dreapta candidat)
{
actual = new Dreapta;
actual -> panta = anterior -> panta;
actual -> termen = anterior -> termen;
const int mijloc = (stanga + dreapta) >> 1;
const bool rezultat_1 = ((*actual)(stanga) > candidat(stanga));
const bool rezultat_2 = ((*actual)(mijloc) > candidat(mijloc));
if (rezultat_2) { swap(actual -> panta , candidat.panta); swap(actual -> termen , candidat.termen); }
if (stanga != dreapta) {
if (rezultat_1 != rezultat_2) { Update(anterior -> stanga , actual -> stanga , stanga , mijloc , candidat); actual -> dreapta = anterior -> dreapta; }
else { actual -> stanga = anterior -> stanga; Update(anterior -> dreapta , actual -> dreapta , mijloc + 1 , dreapta , candidat); }
}
}
inline int64_t Query (Dreapta* &nod , const int stanga , const int dreapta , const int indice)
{
if (stanga == dreapta || nod == radacina[0])
{ return (*nod)(indice); }
const int mijloc = (stanga + dreapta) >> 1;
return min((*nod)(indice) , (indice <= mijloc ? Query(nod -> stanga , stanga , mijloc , indice) : Query(nod -> dreapta , mijloc + 1 , dreapta , indice)));
}
inline void Parcurgere (const int nod , const int sursa)
{
if (nod != 1)
{ minim[nod] = termen[nod] + 1LL * adancime[nod] * factor[nod] + Query(radacina[sursa] , 1 , 1000000000 , factor[nod]); }
Update(radacina[sursa] , radacina[nod] , 1 , 1000000000 , {-adancime[nod] , minim[nod]});
for (auto vecin : adiacenta[nod]) {
if (vecin.first != sursa)
{
adancime[vecin.first] = adancime[nod] + vecin.second;
Parcurgere(vecin.first , nod);
}
}
}
int main ()
{
int numar_noduri;
cin >> numar_noduri;
for (int indice = 1 ; indice < numar_noduri ; indice++)
{
int nod[2] , distanta;
cin >> nod[0] >> nod[1] >> distanta;
adiacenta[nod[0]].push_back({nod[1] , distanta});
adiacenta[nod[1]].push_back({nod[0] , distanta});
}
for (int indice = 2 ; indice <= numar_noduri ; indice++)
{ cin >> termen[indice] >> factor[indice]; }
radacina[0] = new Dreapta;
radacina[0] -> stanga = radacina[0] -> dreapta = radacina[0];
Parcurgere(1 , 0);
for (int indice = 2 ; indice <= numar_noduri ; indice++)
{ cout << minim[indice] << ' '; }
cout.close(); cin.close();
return 0;
}
