题目描述：

摸鱼摸得无聊的时候，LJY 找到了一款游戏，游戏开始时会给你一个有 $n$ 座城市的地图，城市之间有 $n-1$ 条道路使得所有城市连成一个树形结构。

这些城市中 $1$ 号城市为首都，一座城市 $i$ 的地位 $w_i$ 定义为 $i$ 到首都的简单路径上经过的城市数量。

LJY 观察了会儿地图，他发现每座城市 $x$ 有一个给定的 $a_x$ 表示它的能力值 ，而第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，长度为 $l_i$。

我们定义 $dist(x,y)$ 作为树上从 $x$ 到 $y$ 的简单路径上的道路长度总和。

在游戏中，若城市 $x$ 与城市 $y$ 简单路径上的任意城市 $k$，都满足 $w_k\ge w_x$，并且 $dist(x,y)\leq \large a_y$，我们称城市 $x$ 能控制城市 $y~(y\not=x)$ 。

现在 LJY 可以选择一座城市作为游戏初始城市。而为了游戏后期的顺利发展，LJY 想知道在每个节点 $i$ ($1\le i\le n$) 分别能控制几个节点。

输入格式：

第一行包含一个整数 $n$，表示地图中的城市数量。

第二行有 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ，表示节点 $i$ 的能力值。

之后的 $n-1$ 行，每行有两个正整数。其中第 $i$ 行包含 $u_i,v_i,l_i$，表示第 $i$ 条道路连接 $u_i,v_i$ 两座城市，长度为 $l_i$。

输出格式：

输出一行共 $n$ 个整数，第 $i$ 个数表示城市 $i$ 能控制的城市数量。

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

1 0 1 0 0

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

4 3 2 1 0

数据范围

对于 $100 \%$ 的测试数据，满足：

$1\le n \le 2\times10^5$，

$1\le a_x \le 10^9~(1\le x \le n)$，

$1\le u_i,v_i\le n$，$1\le l_i \le 10^9~(1\le i\le n-1)$。