Vova 向自己保证,他永远不会玩电脑游戏……但最近著名游戏开发公司 Firestorm 发布了他们的最新游戏 World of Farcraft,并变得非常受欢迎。当然,Vova开始演奏它。
现在他尝试解决一个任务。任务是来到一个名为Overcity的定居点并在其中传播谣言。
Vova 知道 Overcity 有 n 个角色。有些角色彼此是朋友,他们分享获得的信息。 Vova 还知道他可以贿赂每个角色,这样他或她就开始散布谣言;第 i 个角色想要 ci 金币来换取散布谣言。当一个角色听到谣言时,他会告诉他所有的朋友,然后他们开始向他们的朋友传播谣言(免费),依此类推。
当所有 n 个角色都知道谣言时,任务完成。 Vova 完成任务至少需要花费多少金币?
如果您认为自己还没有完全理解问题,请查看注释。
输入
第一行包含两个整数 n 和 m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105) — Overcity 中的角色数量和好友对的数量。
第二行包含n个整数ci(0≤ci≤109)——第i个字符要求开始散布谣言的金币数量。
接下来是 m 行,每行包含一对数字 (xi, yi),表示字符 xi 和 yi 是朋友(1 ≤ xi, yi ≤ n, xi ≠ yi)。保证每对最多列出一次。
输出
打印一个数字——Vova 完成任务所需花费的最低金币数量。
示例
输入 #1
5 2 2 5 3 4 8 1 4 4 5
输出 #1
10
输入 #2
10 0 1 2 3 4 5 6 7 8 9 10
输出 #2
55
输入 #3
10 5 1 6 2 7 3 8 4 9 5 10 1 2 3 4 5 6 7 8 9 10
输出 #3
15
注意
在第一个示例中,最佳决策是贿赂第一个角色(他将谣言传播给第四个角色,第四个角色将谣言传播给第五个角色)。 Vova 还必须贿赂第二个和第三个角色,让他们知道谣言。
在第二个例子中,Vova 必须贿赂所有人。
在第三个示例中,最佳决策是贿赂第一个、第三个、第五个、第七个和第九个角色。