题目描述

题目译自 XXI Olimpiada Informatyczna — III etap Turystyka

Bajtazar 国王坚信，景点众多的字节城定能吸引无数游客，财源滚滚，填满国库。然而，现实却令人失望。国王命顾问调查，顾问发现，游客稀少的根源是道路网络欠发达。

字节城有 $n$ 座城市和 $m$ 条双向道路，每条路连接两座不同城市，可能经过隧道或高架桥。并非所有城市间都能连通。顾问注意到，现有道路无法支持长途旅行：从任意城市出发，沿道路游览，最多访问 $10$ 座城市就得重复经过某城。

由于财政紧张，Bajtazar 决定不修新路，而是在字节城设立旅游信息点（PIT），由专业人员宣传短途旅行的魅力。每座城市需有一个 PIT，设在本城或与之直接相连的邻城。每座城市的 PIT 建设成本已知。请你帮 Bajtazar 设计最省钱的 PIT 网络。

输入格式

输入第一行包含两个整数 $n, m$ $(2 \leq n \leq 20000, 0 \leq m \leq 25000)$，分别表示字节城的城市数和道路数。城市编号为 $1$ 到 $n$。

第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$ $(0 \leq c_i \leq 10000)$，$c_i$ 表示在 $i$ 号城市建 PIT 的成本。

接下来的 $m$ 行描述道路，每行两个整数 $a_i, b_i$ $(1 \leq a_i < b_i \leq n)$，表示 $a_i$ 号和 $b_i$ 号城市间有道路。每对城市间至多有一条路。

输出格式

输出一行，一个整数，表示建设所有 PIT 的总成本。

6 6
3 8 5 6 2 2
1 2
2 3
1 3
3 4
4 5
4 6

7

为最小化成本，应在 $1, 5, 6$ 号城市建 PIT，总成本为 $3 + 2 + 2 = 7$。

附加样例

1. $n=10, m=9$，道路形成长度为 $10$ 的路径；
2. $n=10, m=45$，每对城市间都有道路；
3. $n=20000, m=19998$，除 $1, 2$ 号城市外，每城有一条路通往 $1$ 或 $2$。

数据范围与提示

对于 $20\%$ 的数据，$n \leq 20$。