问题描述

JAG王国的人们讨厌冗余。例如，JAG王国中的$N$个城市只通过$N-1$条双向道路相连，以使任意城市可以通过一些道路到达任何城市。在这个条件下，任意两个城市之间的路径数目恰好为1。这是一个非冗余的道路网络 :)

有一天，作为JAG王国的一名居民，你决定尽可能多地驾车游览王国中的城市。你将使用的汽车有一个无限大的油箱，但最初油箱是空的。你的汽车每行驶1公里消耗1升汽油。

每个城市都有一个加油站，你可以在城市$x$的加油站给你的汽车供应$g_x$升汽油。当然，在你的旅行中你可以选择不访问某些加油站。但是你不会在同一个加油站多次加油，因为这是多余的。王国中的每条道路都有两个城市之间的距离：第$i$条道路的距离是$d_i$公里。当然，你不会重复经过同一个城市或同一个道路，因为这是多余的。

如果储存的汽油数量为零，汽车就无法行驶，因此你的旅行会在那里结束。但是，你可能会为初始为空的油箱而担心。别担心，你可以从王国中的任意一个加油站出发。此外，每条道路直接连接其两端的加油站（因为非冗余精神避免了在城市中的多余移动），因此即使你的汽车油箱在你到达城市时变为空，你依然可以给你的汽车供应汽油。

你的任务是编写一个程序，计算在非冗余策略下你可以游览的最大城市数量。

输入

输入只包含一个测试用例。

$N$
$g_1$ … $g_N$
$a_1$ $b_1$ $d_1$
…
$a_{N-1}$ $b_{N-1}$ $d_{N-1}$

第一行包含一个整数$N$($1 \\le N \\le 100{,}000$)，表示JAG王国中的城市数量。第二行包含$N$个整数：其中第$i$个整数是$g_i$($1 \\le g_i \\le 10{,}000$)，表示可以在城市$i$的加油站提供的汽油量。接下来的$N-1$行给出了道路的信息：其中第$j$行包含$a_j$和$b_j$，表示第$j$条道路双向连接城市$a_j$和$b_j$($1 \\le a_j, b_j \\le N$，$a_j \\ne b_j$)，距离为$d_j$($1 \\le d_j \\le 10{,}000$)。你可以假设王国中的所有城市都通过道路连接。

输出

打印在约束条件下你可以从任意一个城市出发游览的最大城市数量。

示例输入1

5
5 8 1 3 5
1 2 4
2 3 3
2 4 3
1 5 7```

### 示例输出1

```plain
4```

* * *

### 示例输入2

```plain
2
10 1
1 2 10```

### 示例输出2

```plain
2```

* * *

### 示例输入3

```plain
5
1 3 5 1 1
1 2 5
2 3 3
2 4 3
1 5 5```

### 示例输出3

```plain
3```