题目描述

农夫约翰计划举办一场大型奶牛集会，来自各地的奶牛都将前来参加。他需要选择一个最佳地点来举办集会。

农场共有 $N$（$1\leq N\leq 10^5$）个农场节点，由 $N-1$ 条道路连接成一棵树（任意两个农场之间恰好有一条路径）。第 $i$ 条道路连接农场 $A_i$ 和 $B_i$，长度为 $L_i$（$0 \leq L_i \leq 10^3$）。

第 $i$ 个农场中居住着 $C_i$（$0 \leq C_i \leq 10^3$）只奶牛。集会可以在任意一个农场举行。

如果选择农场 $X$ 作为集会地点，则不方便程度定义为所有奶牛到达 $X$ 的路程之和。具体地，若农场 $i$ 到 $X$ 的距离为 $d(i,X)$，则不方便程度为 $\sum_{i=1}^{N} C_i \times d(i,X)$。

请帮约翰找到使不方便程度最小的集会地点，并输出该最小不方便值。

输入格式

第 $1$ 行一个整数 $N$。

第 $2$ 到 $N+1$ 行：第 $i+1$ 行有一个整数 $C_i$。

第 $N+2$ 到 $2N$ 行：第 $i+N+1$ 行为三个整数 $A_i$、$B_i$ 和 $L_i$。

输出格式

一行一个整数，表示最小的不方便值。

样例

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

15

提示

$1\leq N\leq 10^5$，$1\leq A_i\leq B_i\leq N$，$0 \leq C_i,L_i \leq 10^3$。