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?
Input
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$.
Output
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.