某个国家的交通网络由 $N$ 个城市（编号为 $1$ 到 $N$）和连接它们的 $N-1$ 条道路组成，所有城市都是连通的。对于每条道路，其长度（单位：千米）是已知的；在每个城市中，都设有一个拥有一定油量的加油站。

由于几年前席卷该国的燃料短缺，领先的运输机构决定对城市之间运输货物的能力进行一项调查。运输货物的卡车每行驶一千米消耗一单位燃料。如果卡车在离开某个城市时，其油箱中的油量大于或等于这两个城市之间的距离，则认为在两个相邻城市之间的行驶是可行的。每次卡车到达一个城市时，卡车的油箱可以加一次油，加油量不超过该城市加油站的油量。调查的最终评估定义为满足以下条件的有序城市对 $(A, B)$ 的数量：假设卡车在起点时油箱为空（在旅程开始时，卡车可以在城市 $A$ 的加油站加油），卡车能够从城市 $A$ 行驶到城市 $B$。

为了简化研究，考虑了以下假设：

• 卡车的油箱容量是无限的。
• 从城市 $A$ 出发前往城市 $B$ 的卡车直接行驶到城市 $B$，即在旅途中不会多次访问任何城市（不重复经过同一个城市）。

输入格式

第一行包含一个整数 $N$（$1 \le N \le 100\,000$），表示城市的数量。

第二行包含 $N$ 个整数 $A_i$（$1 \le A_i \le 10^9$），表示第 $i$ 个城市的加油站拥有的油量。

接下来的 $N-1$ 行，每行包含三个整数 $U, V$（$1 \le U, V \le N, U \neq V$）和 $W$（$1 \le W \le 10^9$），描述一条连接城市 $U$ 和 $V$ 且长度为 $W$ 千米的道路。

输出格式

输出调查的最终评估结果（即满足条件的有序城市对数量）。

子任务

在价值 $20\%$ 的测试数据中，满足 $N \le 5000$。

在价值 $40\%$ 的测试数据中，城市网络将形成一条链，即每个城市 $x$（$1 \le x < N$）都与城市 $x + 1$ 相连。

样例

输入样例 1

2
3 1
1 2 2

输出样例 1

1

说明 1

唯一可行的旅程是从城市 1 到城市 2。从城市 2 到城市 1 的旅程是不可行的，因为在从城市 2 出发前，卡车油箱中的油量不可能超过 1 单位。

输入样例 2

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

输出样例 2

5

说明 2

可行旅程的城市对为：$(1, 2)$，$(3, 2)$，$(4, 5)$，$(5, 1)$ 和 $(5, 4)$。

输入样例 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

输出样例 3

29