Description

中科院有$n$个研究所（编号$1$~$n$），被$n-1$条双向道路连接，呈树形结构。

第$i$个研究所共有$A_i$个研究牲。

第$i$天早上，国科大所有的研究生沿最短路走到第$i$个研究所参加学术会议，晚上再原路返回。

一个研究生通过第$j$条通道一次（即一人次），需要道路维护部门支付$w_j$的维护费用。

道路维护部门想知道第$n$天结束之后，对于每一条通道，共需要支付多少费用。

Format

Input

第一行一个整数$n$，表示研究所的数量。

接下来一行，$n$个整数，表示$A_1$~$A_n$。

第$3$到第$n+1$行，每行包含$3$个整数。第$i$行包含三个整数$u_{i-2},v_{i-2},w_{i-2}$，表示第$i-2$条道路所连接的两个研究所的编号，以及一人次通过这条通道的费用。

Output

共$n-1$行，每行一个整数。

第$i$行的整数表示对于第$i$条通道所需支付的维护费用。

Samples

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

24
60
56

Limitation

对于$100\%$的数据，$1\leq n \leq 200,000$，$1\leq A[i]\leq 10,000$，$1\leq w[i] \leq 10,000$。