CF893C Rumor

Vova 曾经发誓再也不玩电脑游戏……但最近 Firestorm——一家著名的游戏开发公司——发布了他们最新的游戏 World of Farcraft，并且这款游戏迅速走红。当然，Vova 也开始玩这款游戏。 现在他试图完成一个任务。任务要求他前往一个名为 Overcity 的定居点，并在其中散布一个谣言。 Vova 知道，Overcity 中有 $n$ 个角色。有些角色彼此是朋友，并且他们会共享获得的信息。此外，Vova 知道他可以贿赂每个角色，让他或她开始传播谣言；第 $i$ 个角色会要求 $c_{i}$ 个金币作为散布谣言的报酬。当某个角色听到谣言后，他会将谣言告诉所有朋友，这些朋友又免费将谣言传播给他们的朋友，以此类推。 当所有 $n$ 个角色都知道谣言时，任务才算完成。Vova 需要花费的最少金币是多少，才能完成这个任务？ 如果你觉得题意还有疑问，可以参看题注说明。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 10^{5},\ 0 \leq m \leq 10^{5}$），分别表示 Overcity 中的角色数和朋友关系的对数。 第二行包含 $n$ 个整数 $c_{i}$（$0 \leq c_{i} \leq 10^{9}$），第 $i$ 个角色要求的金币数。 接下来 $m$ 行，每行包含一对整数 $(x_{i}, y_{i})$，表示第 $x_{i}$ 个与第 $y_{i}$ 个角色是朋友关系（$1 \leq x_{i}, y_{i} \leq n$，$x_{i} \neq y_{i}$）。保证每一对只出现一次。

输出一个整数，表示 Vova 至少要花费多少金币才能完成这个任务。

在第一个样例中，最好贿赂第一个角色（他会将谣言传播给第 4 个角色，第 4 个再传播给第 5 个）。另外，Vova 还需要贿赂第 2 个和第 3 个角色，这样他们才能知道谣言。 在第二个样例中，Vova 必须贿赂每一个人。 在第三个样例中，最优策略是贿赂第 1、3、5、7、9 号角色。 由 ChatGPT 5 翻译