题面描述

Timothy 打算收集编号为 $1\sim n$ 的 $n$ 种魔法药剂，其中每种药剂有两种形态：红色版本与蓝色版本。

获得药剂的方式如下：

• 直接购买：购买一瓶第 $i$ 种红色版本药剂需要花费 $a_i$​ 金币；
• 调配合成：若已拥有红色版本的第 $b_i$​ 种与第 $c_i$​ 种药剂，可分别消耗一瓶，调配得到蓝色版本的第 $i$ 种药剂，调配本身不额外花费金币（仅需保证两种原料存在）。

Timothy 不关心颜色，只要求最终至少拥有 $1\sim n$ 每种药剂中的任意一种形态（红或蓝）。请计算他所需支付的最小总金币数。

输入描述

第一行输入一个整数 $n(1\leqslant n\leqslant 10^5)$，表示药剂种类数量。

第二行输入 $n$ 个整数 $a_1,a_2,a_3,\cdots,a_n(1\leqslant a_i\leqslant 10^4)$，依次表示直接购买一瓶第 $i$ 种红色药剂的价格。

接下来 $n$ 行，第 $i$ 行输入两个整数 $b_i,c_i(1\leqslant b_i,c_i\leqslant n)$，表示合成蓝色版本第 $i$ 种药剂所需的两种红色药剂的编号。

输出描述

输出一个整数，表示获得 $n$ 种不同药剂所需支付的最小金币数。

样例

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

16

一种最优方案：

• 直接购买第 $1,2,4,5$ 种红色药剂，花费 $2+4+1+3=10$；
• 利用红色的 $1,2$ 调配得到第 $3$ 种蓝色药剂，花费 $2+4=6$；

最终花费 $10+6=16$，满足拥有 $1\sim 5$ 的不同药剂。