题目描述

有一个国家有 $n$ 个城市，这 $n$ 个城市构成了一棵树。每个城市初始时有一个师的军队，第 $i$ 个师的优先级为 $a_i$。现在所有师都要沿最短路径去到首都 $1$ 号城市。第 $i$ 条边连接的两个城市 $u_i, v_i$ 之间有一辆火车，每天可以被 $c_i$ 个师通过。如果同一天有多个师需要通过第 $i$ 条边，$a$ 值低的师先通过。从第 $0$ 天开始算，求出每个点到达首都的时间。

输入格式

第一行一个整数 $n$，$1 \le n \le 5000$。

第二行 $n$ 个整数 $a_i$，$1 \le a_i \le 10^9$。

接下来 $n-1$ 行，每行 $3$ 个整数 $u_i, v_i, c_i$。

输出格式

一行 $n$ 个整数 $t_i$，表示每个点到达首都的时间。

4
40 10 30 20
1 2 1
2 3 1
4 2 1

0 1 3 2

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

0 1 4 2 3