题目背景

某产业园区的楼宇由通道连成一棵树，管理处计划在楼宇安装监控覆盖所有通道。园区规定入口1号楼必须安装监控，需要算出满足全部要求的最低安装总成本。

题目描述

给定一棵包含 $n$ 个楼宇的无根树，每栋楼宇安装监控有对应成本 $w_i$。 在某栋楼宇安装监控，所有与它直接相连的通道都会被覆盖；每条通道至少一端楼宇装有监控才算合规。 额外强制要求：1号楼宇必须安装监控，不允许空置。 请求出满足所有条件的最小总安装成本。

输入描述

第一行一个整数 $n$，代表园区楼宇总数。 第二行 $n$ 个整数，第 $i$ 个数为第 $i$ 栋楼宇安装监控的花费 $w_i$。 接下来 $n-1$ 行，每行两个整数 $u,v$，代表楼宇 $u$ 和 $v$ 之间连通一条通道。 楼宇编号：$1 \le u,v \le n$。

输出描述

输出一行一个整数，为全覆盖通道且1号楼必装监控的最小总花费。

输入样例1

4
5 1 3 4
1 2
2 3
2 4

输出样例1

6

样例解释：强制1号楼必须装（成本5）。如果只装1号楼，楼宇2、3、4均无监控，通道2-3、2-4两端都没有监控，不符合覆盖要求。因此需要额外在2号楼安装监控（成本1），总花费 $5+1=6$。

输入样例2

5
10 2 1 5 7
1 2
1 3
3 4
3 5

输出样例2

11

样例解释：1号楼强制安装（花费10），3号楼安装（花费1），合计11；无法不选1号，因此不能使用不合法的2+1方案。

数据范围

$2 \le n \le 1500$ $1 \le w_i \le 1000$ 输入保证为合法树，无自环、无重复通道。