A91489.Welcome24ever 和集会

Welcome24ever 正在筹划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这次活动。当然，他希望选择一个对所有奶牛都尽量方便的地点来举办集会。

有 $N$ 个农场，这些农场由 $N-1$ 条双向道路连接，形成一棵树结构（从任意一个农场都能到达其它所有农场）。
第 $i$ 条道路连接农场 $A_i$ 和农场 $B_i$，道路长度为 $L_i$。

集会可以在 $N$ 个农场中的任意一个举行。
每个农场 $i$ 中居住着 $C_i$ 只奶牛。

如果选择在农场 $X$ 举办集会，则每只奶牛都要从自己居住的农场出发，沿着最短路径走到农场 $X$。
我们把不方便程度定义为：所有奶牛为前往集会地点而行走的路程之和。
例如，农场 $i$ 到农场 $X$ 的最短距离为 $d(i,X)$，则农场 $i$ 的所有奶牛一共要走的路程为 $C_i \times d(i,X)$，
总不方便程度就是对所有农场 $i$ 的 $C_i \times d(i,X)$ 求和。

请你帮 Welcome24ever 选择一个合适的农场作为集会地点，使得总不方便程度最小，并输出这个最小值。

• 第 $1$ 行：一个整数 $N$，表示农场数量。
• 第 $2$ 行到第 $N+1$ 行：第 $i+1$ 行包含一个整数 $C_i$，表示第 $i$ 个农场中的奶牛数量。
• 第 $N+2$ 行到第 $2N$ 行：第 $(i+N+1)$ 行包含三个整数 $A_i, B_i, L_i$，表示一条连接农场 $A_i$ 和 $B_i$ 的道路，长度为 $L_i$。

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

数据范围与说明

• $1 \leq N \leq 10^5$；
• $1 \leq A_i \leq B_i \leq N$；
• $0 \leq C_i, L_i \leq 10^3$；
• 给定的道路保证所有农场构成一棵树（连通且无环）。