Problem Description

Given a tree where each edge has a length. Each node contains a landmine, and the $i$-th node's landmine has an explosion radius of $r_i$.

We define $dist(i,j)$ as the shortest distance between vertex $i$ and vertex $j$ in the tree. In other words, $dist(i,j)$ is the sum of edge lengths along the unique simple path between vertex $i$ and vertex $j$.

When the landmine at vertex $i$ explodes, after one second, all landmines within distance $r_i$ from vertex $i$ will explode together. In other words, for all landmines $j$ satisfying $dist(i,j) \leq r_i$, if they have not exploded yet, they will be detonated one second after the landmine at vertex $i$ explodes.

For each $i = 2, 3, \dots, n$, you want to calculate how long it will take for the first landmine at vertex $1$ to be detonated after detonating the landmine at vertex $i$, or if it can never be detonated.

Input

The input consists of multiple test cases. The first line contains a single integer $T$ ($1 \le T \le 100$) - the number of test cases. Description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \le n \le 10 ^ 5$).

The second line contains $n - 1$ integers $r_2, r_3, \dots, r_n$ ($0 \le r_i \le 10 ^ {18}$).

Each of the following $n - 1$ lines contains three integers $u, v, w$ ($1\leq u,v\leq n$, $u\neq v$, $1 \le w_i \le 10 ^ {12}$) - an edge between $u$ and $v$ with a length of $w$.

It's guaranteed that $\sum n \leq 10^6$.

Output

For each test case, print $n - 1$ integers - the time in seconds after detonating the landmine at vertex $i$, at which the first landmine at vertex $1$ will be detonated. If it can never be detonated, output $-1$.

2
3
2 6
1 2 3
2 3 2
5
1 1 1 1
1 2 1
1 3 1
2 4 1
2 5 2

2 1
1 1 2 -1