Statement

Timothy plans to collect $n$ types of magic potions, numbered $1\sim n$, each of which has two forms: a red version and a blue version.

The way to obtain the potion is as follows:

• Direct purchase: Purchasing one bottle of the $i$th type of red version potion costs $a_i$ gold coins;
• Blending and Synthesis: If you already possess the red versions of the $b_i$th and $c_i$th potions, you can consume one bottle of each to blend and obtain the blue version of the $i$th potion. The blending process itself does not cost additional gold coins (as long as both raw materials are present).

Timothy doesn't care about the color, and only requires that he ultimately has at least one form (red or blue) of each of the $1\sim n$ potions. Please calculate the minimum total number of gold coins he needs to pay.

Input

Input an integer $n(1\leqslant n\leqslant 10^5)$ in the first line, representing the number of types of potions.

Input $n$ integers $a_1, a_2, a_3, \cdots, a_n (1 \leqslant a_i \leqslant 10^4)$ in the second line, representing the prices of directly purchasing one bottle of the $i$th type of red potion in sequence.

Next, there are $n$ lines, and the $i$th line contains two integers $b_i,c_i(1\leqslant b_i,c_i\leqslant n)$ representing the IDs of the two red potions required to synthesize the $i$th type of blue potion.

Output

Output an integer representing the minimum number of gold coins required to obtain $n$ different potions.

Samples

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

16

An optimal solution:

• Purchase the $1st, 2nd, 4th, 5th$ red potions directly, costing $2+4+1+3=10$;
• Use $1$ red $2$ to prepare the $3$rd blue potion, costing $2+4=6$;

The final cost is $10+6=16$, satisfying the requirement of having different potions from $1\sim 5$.