Problem Description

In a country, there are $n$ cities, each equipped with a gas station having a fuel reserve of $a_i$. There are $n-1$ paths connecting these cities in a tree structure.

A truck can travel from city $u$ to city $v$ if its fuel level is not less than the distance between $u$ and $v$. Whenever the truck arrives at a city, it can refill its tank up to the amount available at the gas station.

Assuming the truck's fuel tank is infinitely large, calculate how many ordered pairs $(u,v)$ exist such that a truck starting with zero initial fuel can travel from city $u$ to city $v$.

Note that the truck can only travel on simple paths, meaning it cannot backtrack.

Input Format

The first line contains a positive integer $n$.
The second line contains $n$ positive integers $a_i$, representing the fuel reserves at each gas station.
The next $n-1$ lines each contain three positive integers $u, v, w$, indicating a path of length $w$ between cities $u$ and $v$.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

2
3 1
1 2 2

Sample Output #1

1

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

Notes/Hints

Sample 1 Explanation:

The only feasible pair is $(1,2)$, meaning only the path $1\rightarrow 2$ is possible.

Data Range:

For $20\%$ of the data:
$1 \le n \le 5000$
For $40\%$ of the data:
The tree is a linear chain
For $100\%$ of the data:
$1 \le n \le 10^5$
$1 \le u, v \le n$
$1 \le w, a_i \le 10^9$

见题面 Input 部分

见题面 Output 部分