题目描述

某个城市由 $n$ 个社区构成，这些社区之间由 $n-1$ 条道路连接，且任意两个社区之间都可以经由一些道路到达。

也就是说，如果将每个社区看成一个点，将道路看成连接两个点的一条边，则这个城市相当于是一棵树。

第 $i(1 \le i \le n)$ 个社区一共有 $a_i$ 个人。

现在需要在某个社区开一家医院，使得代价最低。

在第 $i$ 个社区开一家医院的代价 $cost_i$ 是这个城市中每一个人从他所在的社区到第 $i$ 个社区的路径长度之和。即，若我们用 $dist(i, j)$ 表示第 $i$ 个社区经由城市的道路到达第 $j$ 个社区的路程，则

求：最小总代价。

输入格式

第一行，一个整数 $n$，表示社区数。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$，以空格分隔，表示每个社区的人数。

接下来 $n-1$ 行，每行包含三个整数 $u_i, v_i, w_i$，表示存在一条连接社区 $u_i$ 和 $v_i$ 的道路，这条道路的长度为 $w_i$。

输出格式

输出一个整数，表示最小代价。

样例

3
1 2 3
1 2 1
2 3 2

7

6
3 2 5 7 2 8
1 2 7
2 3 5
2 4 2
4 5 11
4 6 8

152

9
1 1 1 1 1 1 1 1 1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1

20

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 10$，$a_i \le 10$，$w_i \le 10$
• 对于 $50\%$ 的数据，$n \le 1000$，$a_i \le 1000$，$w_i \le 1000$
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le a_i \le 10^5$，$1 \le w_i \le 10^5$，数据保证这是一棵树