Compania lui Jimmy are n plantații cu flori. Pentru fiecare plantație se cunoaște tipul florilor cultivate, respectiv câte tone de flori au fost produse anul acesta. Se cunoaște că plantațiile cu flori sunt conectate prin n - 1 drumuri astfel încât la fiecare plantație se poate ajunge de la oricare altă plantație și există un singur mod de ajunge de la plantația x la plantația y , pentru fiecare 1 ≤ x, y ≤ n. De asemenea, știm și distanța în km pentru fiecare dintre cele n - 1 drumuri.

Cerința

Jimmy vrea să aducă toate florile de același tip în același loc, cu cost minim de transport. Dacă avem a tone de flori şi vrem să le trimitem pe o distanță de b kilometri, costul transportului este a * b. Pentru fiecare tip de floare Jimmy vrea să determine costul minim de transport pentru a aduce toate florile de același tip la un loc.

Date de intrare

Pe prima linie se va găsi numărul n, apoi, pe cea de-a doua linie, n litere mici separate între ele prin câte un spațiu, care simbolizează tipul de floare produs pe plantația i (fiecare tip de floare este o literă mică a alfabetului englez). Pe cea de-a treia linie se găsesc n numere întregi care reprezintă câte tone din fiecare floare au fost produse pe plantația i. Pe fiecare dintre următoarele n - 1 linii se găsesc trei numere naturale x, y, d, cu semnificația că există drum direct între plantațiile x şi y, iar numărul d reprezintă distanța de la x la y.

Date de ieșire

Pe prima linie se afișează 26 de numere separate prin spațiu, al i-lea număr reprezentând costul minim de transport pentru tipul de floare specificat de litera de pe poziția i în alfabetul englez (răspunsurile sunt în ordinea în care literele se găsesc în alfabet).

Restricții și precizări

• 4 ≤ n < 200 001.
• Fiecare dintre numerele din datele de intrare este un număr natural mai mic decât 200 001.
• Destinaţia finală a fiecărui transport este una dintre cele n plantaţii existente.
• Dacă există litere care nu reprezintă codul tipului unei flori, atunci costul minim de transport pentru acel tip este 0.
• Pentru 20% din teste, n < 1000.
• Pentru alte 25% din teste, n < 100 000.

Exemplu:

Intrare

4
a b a b
2 4 4 3
1 3 4
3 4 2
1 2 5

Ieșire

8 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0