h2. Date de intrare

Fişierul de intrare $harbingers.in$ ...

Fişierul de intrare $harbingers.in$ contine un numar natural $N$, numarul de orase din tinutul Moldovei. Pe fiecare din urmatoarele $N-1$ linii se afla 3 intregi $u v d$, separati de cate un spatiu, care descriu o poteca de lungime $d$ intre orasele numerotate cu $u$ si $v$. Urmeaza apoi alte $N-1$ perechi de intregi, cate o pereche pe linie. Perechea a $i$-a, $S{~i~} V{~i~}$, descrie caracteristicile mesagerului din orasul $(i+1)$: $S{~i~}$ este numarul de minute necesar mesagerului de a se pregati de calatorie, iar $V{~i~}$ este numarul de minute necesar mesagerului pentru a calatori un kilometru. Nu exista niciun mesager in capitala.

h2. Date de ieşire

În fişierul de ieşire $harbingers.out$ ...

În fişierul de ieşire $harbingers.out$ trebuie sa se afle exact $N-1$ intregi. Al i-lea
 
The output file harbingers.out should consist of exactly one line containing N-1 integers.
The ith number represents the minimum time, in minutes, required to send a message from the
(i+1)th town to the capital.

h2. Restricţii