Magic boy Bi Luo with his excited tree

Bi Luo is a magic boy, he also has a migic tree, the tree has $N$ nodes , in each node , there is a treasure, it's value is $V[i]$, and for each edge, there is a cost $C[i]$, which means every time you pass the edge $i$ , you need to pay $C[i]$.

You may attention that every $V[i]$ can be taken only once, but for some $C[i]$ , you may cost severial times.

Now, Bi Luo define $ans[i]$ as the most value can Bi Luo gets if Bi Luo starts at node $i$.

Bi Luo is also an excited boy, now he wants to know every $ans[i]$, can you help him?

First line is a positive integer $T( T \leq 10^4)$ , represents there are $T$ test cases.

Four each test：

The first line contain an integer $N$$( N \leq 10^5 )$.

The next line contains $N$ integers $V[i]$, which means the treasure’s value of node $i ( 1 \leq V[i] \leq 10^4 )$.

For the next $N - 1$ lines, each contains three integers $u , v , c$ , which means node $u$ and node $v$ are connected by an edge, it's cost is $c (1 \leq c \leq 10^4 )$.

You can assume that the sum of $N$ will not exceed $10^6$.

For the i-th test case , first output Case #i: in a single line , then output $N$ lines , for the i-th line , output $ans[i]$ in a single line.

1
5
4 1 7 7 7 
1 2 6
1 3 1
2 4 8
3 5 2

Case #1:
15
10
14
9
15

UESTC

2016中国大学生程序设计竞赛 - 网络选拔赛