Berland王国是由n个城市组成的集合,这些城市通过n - 1条铁路相互连接。每条道路恰好连接两个不同的城市。首都位于城市 1。每个城市都有一种从那里乘坐铁路到达首都的方法。
在第i个城市中有一个士兵师,编号为i,每个师的特点是有多个ai。它代表优先级,数字越小,该划分的优先级越高。 ai的所有值都是不同的。
有一天,贝尔兰国王贝尔大帝宣布了总动员,为此,各师必须抵达首都。除首都外,每天都有火车从每个城市出发。所以每天正好有 n - 1 趟出发火车。每趟列车均开往首都,并于第二天在铁路的另一端结束运行。它有一些有限的容量 cj,以该列车可以一次性运输的最大分区数表示。每趟列车都朝着缩短到首都距离的方向行驶。因此,每列火车恰好经过一条从一个城市到邻近城市(停靠点)前往首都的铁路。
在城市中的分区中,首先,人工智能数量最少的分区上车,然后是次少的分区,依此类推,直到火车满了或所有分区都装载完毕。所以一个师在一个城市停留几天是可能的。
火车从一个城市到另一个城市的行驶时间始终等于 1 天。所有师同时开始移动并最终到达首都,从那里他们不再去其他任何地方。每个师都沿着一条简单的路径从其城市前往首都,无论这段旅程需要多长时间。
你的目标是找出每个师需要多少天才能到达贝尔兰首都。倒计时从第 0 天开始。
输入
第一行包含单个整数 n (1 ≤ n ≤ 5000)。这是贝尔兰的城市数量。第二行包含n个空格分隔的整数a1,a2,...,an,其中ai表示分区的优先级,位于第i个城市。所有数字 a1、a2、...、an 都不同 (1 ≤ ai ≤ 109)。然后n-1行包含铁路道路的描述。每个描述由三个整数vj、uj、cj组成,其中vj、uj是第j条铁路连接的城市数量,cj代表该道路上列车的最大载客量(1≤vj,uj≤n,vj≠uj,1≤cj≤n)。
输出
打印序列 t1, t2, ..., tn,其中 ti 代表城市 i 的分区到达首都所需的天数。用空格分隔数字。
示例
输入 #1
4 40 10 30 20 1 2 1 2 3 1 4 2 1
输出 #1
0 1 3 2
输入 #2
5 5 4 3 2 1 1 2 1 2 3 1 2 4 1 4 5 1
输出 #2
0 1 4 2 3