Radio Prize

This problem was used in the following GFU competitions:

GFU 2024 D1 Q4

Problem

All boring tree-shaped lands are alike, while all exciting tree-shaped lands are exciting in their own special ways. What makes Treeland more exciting than the other tree-shaped lands are the raddest radio hosts in the local area: Root and Leaf. Every morning on FM 32:33 (repeating of course), Root and Leaf of The Full Depth Morning Show serve up the hottest celebrity gossip and traffic updates.

The region of Treeland is made of n cities, connected by n - 1 roads such that between every pair of cities there is exactly one simple path. The ith road connects cities ui and vi, and has a toll of wi.

To reward their loyal listeners, The Full Depth Morning Show is giving away a number of travel packages! Root and Leaf will choose n - 1 lucky residents from the city that sends them the most fan mail. Each of those residents then gets a distinct ticket to a different city in Treeland.

Each city in Treeland has its own tax on prizes: ti. Let du,v be the sum of the tolls on each road on the only simple path from city u to v. For a trip from city u to city v, the cost of that trip is then (tu + tv)du,v.

The shock jocks haven’t quite thought through how much their prize is worth. They need to prepare a report to the radio executives, to summarize the expected costs. For each city that could win the prize, what is the total cost of purchasing all the tickets?

Input

The first input will contain a single integer x that indicates the number of test cases that follow. Each test case will begin with a single integer n (1 <= n <= 100,000). The next input is n integers ti (1 <= ti <= 1,000), the tax in each city. The following n - 1 inputs each have 3 integers, ui; vi, wi, meaning the ith road connects cities ui and vi (1 <= ui; vi <= n), with a toll of wi (1 <= wi <= 1,000).

Output

For each test case, output n lines followed by a blank line. On the ith line, output a single integer: the cost of purchasing tickets if city i wins the contest.

Example (Basic Test)

Example Input:

2 5 3 4 1

1 2 2

2 4 5

4 3 3

5 2 6

4 3 3 4 3 3

1 3 2

2 1 1

1 4 6

4 5 6

6 4 2

Example Output:

130

159

191

163

171

209

206

232

209

336

232

Tips/Tricks/Hints

Page updated

Google Sites

Report abuse