The traffic network in one country consists of $N$ cities (marked by numbers from $1$ to $N$) and $N-1$ roads connecting them in a way that all cities are connected. For each road, its length in kilometers is known, and in each city there is a gas station with a certain amount of fuel.

Due to the fuel shortages that hit the country a few years ago, the leading transport agency has decided to conduct a survey on the ability to transport goods between cities. Trucks transporting goods consume one unit of fuel per kilometer and the journey between two neighboring cities is considered possible if the amount of fuel in a truck's fuel tank at the time of leaving the city is greater than or equal to the distance between the cities. Each time when a truck is in a city, the truck's fuel tank can be filled up by an amount not greater than the amount of fuel in that city's gas station. The final assessment of the survey is defined as the number of ordered pairs of cities $(A,B)$ such that it is possible to travel from city $A$ to city $B$ under the assumption that a truck starts the journey with an empty fuel tank (at the beginning of the journey the fuel tank should be filled at the gas station in city $A$).

For the simplicity of the research, the following assumptions have been taken into account:

• A truck's fuel tank has unlimited capacity.
• A truck leaving from the city $A$ travels directly to the city $B$, i.e. it does not visit any city on its journey more than once.

Input

The first line contains the integer number $N$ $(1\le N\le 100000)$, the number of cities.

In the second line there are $N$ integer numbers $A_i$ $(1\le A_i\le {10}^9)$, the amount of fuel at the gas station in the $i^{th}$ city.

In the following $N-1$ rows there are three integer numbers $U,V$ $(1\le U,V\le N,U\ne V)$ and $W$ $(1\le W\le {10}^9)$ describing the road between cities $U$ and $V$ of length $W$ kilometers.

Output

Print the final assessment of the survey.

Scoring

In the test samples totally worth 20% of the points it will hold $N\le 5000$.

In the test samples totally worth 40% points the network of cities will form a chain, i.e. each city $x$ $(1\le x<N)$ will be connected to city $x+1$.

Sample Input 1

2
3 1
1 2 2

Sample Output 1

1

Explanation for Sample Output 1

The only possible way to travel is from city $1$ to city $2$. The journey from city $2$ to city $1$ is not possible because before departure from city $2$ a truck cannot have more than $1$ unit of fuel in the fuel tank.

Sample Input 2

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

Sample Output 2

5

Explanation for Sample Output 2

Pairs of cities among which the journey is possible $(1,2)$, $(3,2)$, $(4,5)$, $(5,2)$ and $(5,4)$.

Sample Input 3

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

Sample Output 3

29