CF82C.General Mobilization

The Berland Kingdom is a set of n cities connected with each other with n - 1 railways. Each road connects exactly two different cities. The capital is located in city 1. For each city there is a way to get from there to the capital by rail.

In the i-th city there is a soldier division number i, each division is characterized by a number of a__i. It represents the priority, the smaller the number, the higher the priority of this division. All values of a__i are different.

One day the Berland King Berl Great declared a general mobilization, and for that, each division should arrive in the capital. Every day from every city except the capital a train departs. So there are exactly n - 1 departing trains each day. Each train moves toward the capital and finishes movement on the opposite endpoint of the railway on the next day. It has some finite capacity of c__j, expressed in the maximum number of divisions, which this train can transport in one go. Each train moves in the direction of reducing the distance to the capital. So each train passes exactly one railway moving from a city to the neighboring (where it stops) toward the capital.

In the first place among the divisions that are in the city, division with the smallest number of a__i get on the train, then with the next smallest and so on, until either the train is full or all the divisions are be loaded. So it is possible for a division to stay in a city for a several days.

The duration of train's progress from one city to another is always equal to 1 day. All divisions start moving at the same time and end up in the capital, from where they don't go anywhere else any more. Each division moves along a simple path from its city to the capital, regardless of how much time this journey will take.

Your goal is to find for each division, in how many days it will arrive to the capital of Berland. The countdown begins from day 0.

贝尔兰王国由 $n$ 座城市组成，这些城市通过 $n-1$ 条铁路彼此相连。每条铁路恰好连接两个不同的城市。首都位于第 1 号城市。对于任意一座城市，均存在一条沿铁路通往首都的路径。

第 $i$ 号城市中驻扎着第 $i$ 支士兵部队，每支部队由一个数值 $a_i$ 表征，该数值代表其优先级：数值越小，优先级越高。所有 $a_i$ 的值互不相同。

某日，贝尔兰国王贝尔·格雷特宣布全国总动员，要求所有部队均须抵达首都。每天，除首都外，每座城市均发出一列火车。因此，每天恰好有 $n-1$ 列火车出发。每列火车朝向首都行驶，并于次日抵达其所经铁路另一端的城市（即终点站）。每列火车具有有限运力 $c_j$，表示其单次最多可运送的部队数量。所有火车均沿缩短至首都距离的方向运行，即每列火车每次仅经过一条铁路，从一座城市驶向邻近的、更靠近首都的城市（并在该城市停靠）。

在每一座城市中，上车顺序按部队优先级由高到低进行：即优先选择 $a_i$ 值最小的部队，其次为次小者，依此类推，直至列车满载或该城市所有部队均已上车。因此，某支部队可能需在某座城市停留多日。

火车从一座城市行驶至相邻城市所需时间恒为 1 天。所有部队同时开始移动，最终全部抵达首都，此后不再离开首都。每支部队均沿其所在城市至首都之间的唯一简单路径行进，无论该旅程耗时多久。

你的任务是：对每支部队，求出其抵达贝尔兰首都所需的天数（计时从第 0 天开始）。

The first line contains the single integer n (1 ≤ n ≤ 5000). It is the number of cities in Berland. The second line contains n space-separated integers _a_1, _a_2, ..., a__n, where a__i represents the priority of the division, located in the city number i. All numbers _a_1, _a_2, ..., a__n are different (1 ≤ a__i ≤ 109). Then n - 1 lines contain the descriptions of the railway roads. Each description consists of three integers v__j, u__j, c__j, where v__j, u__j are number of cities connected by the j-th rail, and c__j stands for the maximum capacity of a train riding on this road (1 ≤ v__j, u__j ≤ n, v__j ≠ u__j, 1 ≤ c__j ≤ n).

第一行包含一个整数 $n$（$1 \leq n \leq 5000$），表示 Berland 国家的城市数量。
第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示位于第 $i$ 号城市的部队的优先级。所有数 $a_1, a_2, \dots, a_n$ 互不相同（$1 \leq a_i \leq 10^9$）。
接下来 $n-1$ 行描述铁路线路。每行包含三个整数 $v_j, u_j, c_j$，其中 $v_j$ 和 $u_j$ 是由第 $j$ 条铁路连接的两个城市编号，$c_j$ 表示在该铁路上运行的列车的最大运载能力（$1 \leq v_j, u_j \leq n$，$v_j \neq u_j$，$1 \leq c_j \leq n$）。

Print sequence _t_1, _t_2, ..., t__n, where t__i stands for the number of days it takes for the division of city i to arrive to the capital. Separate numbers with spaces.

输出序列 $t_1,\,t_2,\,...,\,t_n$，其中 $t_i$ 表示第 $i$ 座城市的部队到达首都所需的天数。各数字之间用空格分隔。