P3577 [POI 2014] TUR-Tourism

国王 Byteasar 认为 Byteotia 是一个充满美丽景色的地方，应该吸引大量游客，他们应该花很多钱，这些钱最终应该流入皇家国库。 但现实并没有达到他的梦想。 因此，国王指示他的顾问调查这个问题。 顾问发现外国人因为 Byteotia 稀疏的道路网络而避开这里。 我们注意到 Byteotia 有 $n$ 个城镇，由 $m$ 条双向道路连接，每条道路连接两个不同的城镇。 这些道路可能经过风景如画的高架桥和不那么美观的隧道。 不能保证每个城镇都可以从其他城镇到达。 顾问观察到当前的道路网络不允许进行长途旅行。 也就是说，无论从哪里开始旅行，都不可能在不经过某个城镇两次的情况下访问超过 10 个城镇。 由于国库资金有限，目前不会修建新的道路。 相反，Byteasar 决定建立一个旅游信息点（TIPs）网络，由官员负责宣传可用的短途旅行。 对于每个城镇，应该在该城镇或通过道路直接连接的城镇之一设立一个 TIP。 此外，每个城镇建设 TIP 的成本是已知的。 通过找到满足上述条件的最便宜的建设 TIP 的方式来帮助国王。

标准输入的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 20\ 000$，$0 \le m \le 25\ 000$），用一个空格分隔，分别指定 Byteotia 的城镇和道路的数量。 城镇编号从 $1$ 到 $n$。 输入的第二行包含 $n$ 个整数 $c_1,c_2,\cdots,c_n$（$0 \le c_i \le 10\ 000$），用空格分隔；数字 $c_i$ 指定在第 $i$ 个城镇建设 TIP 的成本。 接下来是 Byteotia 道路网络的描述。接下来的 $m$ 行中的第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i < b_i \le n$），用一个空格分隔，表示第 $a_i$ 个城镇和第 $b_i$ 个城镇之间有一条道路。任何一对城镇之间最多只有一条（直接）道路。

你的程序应输出一个整数到标准输出：建设所有 TIP 的总成本。

题面翻译由 ChatGPT-4o 提供。