Laupītājs ceļo un meklē dārgumus kādā valstī, kas sastāv no N pilsētām un ir savstarpēji savienotas ar N - 1 ceļiem, tā ka ir iespējams no jebkuras pilsētas nokļūt uz jebkuru citu pilsētu. Katrā pilsētā ir atrodami d[i] dimanti, un ja laupītājs nonāk tajā pilsētā viņš tos visus dabū. Dimantus no pilsētas ir iespējams savākt tikai vienu reizi. i-tais ceļš(1 <= i <= n - 1) savieno pilsētas u[i] un v[i], taču lai ceļotu pa šo ceļu ir jāsamaksā nodeva c[i] dimanti. Laupītājs savu ceļojumu sāk kādā no pilsētām, dodas ceļā pa kādām pilsētām un savāc ceļā esošos dimantus, un pēc tam atgriežas sākotnējā pilsētā. Šādā ceļojumā laupītajs nopelna (pilsētās atrasto dimantu skaits) - (ceļā patērēto dimantu skaits) dimantus(šī summa var būt negatīva). Katrai pilsētai aprēķiniet maksimālo skaitu dimantu, ko laupītājs var nopelnīt ja viņš sāk tajā pilsētā!

Ievaddatu pirmajā rindā ir dots pilsētu skaits n(2 <= n <= 100000). Ievaddatu otrajā rindā ir doti n skaitļi d[i](0 <= d[i] <= 10^9), kas apzīmē dimantu skaitu katrā pilsētā. Katrā no nākamajām n - 1 rindām ir doti trīs skaitļi u[i], v[i] (1 <= u[i], v[i] <= n) un c[i](1 <= c[i] <= 10^9), kuri apzīmē pilsētas kuras savieno viens ceļš(1 <= u[i], v[i] <= n).

Izvaddatu vienīgajā rindā izvadiet n skaitļus, i - tais skaitlis apzīmē maksimālo skaitu dimantu, ko laupītājs var nopelnīt sākot i-tajā pilsētā.

1. testpiemērā sākot 4. pilsētā laupītājs, var nopelnīt 8 dimantus ceļojot pa pilsētām šādā secībā: 4 -> 2 -> 3 -> 5 -> 3 -> 2 -> 4, pilsētās viņš atrod kopā 18 dimantus, taču ceļā patērē 10 dimantus, tātad viņš nopelna 18 - 10 = 8 dimantus

1. apakšuzdevums n <= 16(10 punkti)
2. apakšuzdevums n <= 1000(30 punkti)
3. apakšuzdevums Bez papildus ierobežojumiem(60 punkti)