题目描述

给定一个 $n$ 个点，$m$ 条边的无向图，其中你在第 $i$ 个点建立旅游站点的费用为 $C[i]$。在这张图中，任意两点间不存在节点数超过 $10$ 的简单路径。

请找到一种费用最小的建立旅游站点的方案，使得每个点要么建立了旅游站点，要么与它有边直接相连的点里至少有一个点建立了旅游站点。

输入格式

第一行包含两个正整数 $n,~m(1 \le n \le 2 \times 10^4,~0 \le m \le 2.5 \times 10^4)$，分别表示点数和边数。

第二行包含n个整数，其中第i个数为 $C[i](0 \le C[i] \le 10^4)$，表示在第i个点建立旅游站点的费用。

接下来 $m$ 行，每行两个正整数 $u,~v(1 \le u,~v \le n)$，表示 $u$ 与 $v$ 之间连了一条边，保证没有重边。

输出格式

输出一行一个整数，即最小的总费用。

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

7

提示

分别在 $1$，$5$，$6$ 号站点建立旅游站点。

题目来源

没有写明来源