问题 L: Landmine

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 ri from vertex i will explode together. In other words, for all landmines j satisfyingdist(i,j)≤ri, if they have not exploded yet, they will be detonated one second after the landmine at vertex i explodes.

For each i=2,3,…,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.

The first line of each test case contains one integer n (1≤n≤105).

The second line contains n - 1 integers r2,r3,…,rn (0≤ri≤1018).

Each of the following n - 1 lines contains three integers u, v, w (1≤u,v≤n, u！=v, 1≤wi≤1012) - an edge between u and v with a length of w.

It's guaranteed that ∑n≤106.