You are given a tree (an undirected acyclic graph) in which each edge has a certain length. In each vertex of this tree, there is a mine with a certain blast radius. If a mine explodes, the mines in all vertices at a distance of no more than the blast radius of this mine will also explode. The distance between two vertices is defined as the sum of the lengths of the edges on the simple path between them. Determine, for each mine, how many mines will explode if we detonate this single one "manually". Note that for each mine, its manual detonation is considered independently of the manual detonations of other mines.

Input

The first line of the standard input contains a single integer $n$ ($1 \le n \le 100\,000$), denoting the number of vertices in the tree (and also the number of mines). The vertices of the tree are numbered with integers from $1$ to $n$.

The second line contains $n$ integers $r_1, r_2, \dots, r_n$ ($0 \le r_i \le 10^{18}$), where $r_i$ denotes the blast radius of the mine located at the $i$-th vertex.

Each of the following $n-1$ lines contains three integers $a_i$, $b_i$, and $c_i$ ($1 \le a_i, b_i \le n; 1 \le c_i \le 10^{12}$), which mean that there is an edge of length $c_i$ connecting vertices $a_i$ and $b_i$.

We guarantee that the input contains a valid description of a tree.

Output

The only line of the output should contain $n$ integers, where the $i$-th of them should be equal to the number of mines that will explode if we manually detonate the mine located at the $i$-th vertex of the tree.

Examples

For the input data:

5
8 1 0 4 6
2 4 2
3 1 9
2 5 5
2 1 2

the correct result is:

4 1 1 4 2

Note

The tree in the sample test looks as follows:

When we manually detonate the mine located at the fourth vertex, its explosion will cause the detonation of the mines located at the first and second vertices, and as a result, the mine located at the first vertex will cause the explosion of the mine located at the fifth vertex. Therefore, a total of four mines will explode.