9405 - 修路(road)

通过次数

16

提交次数

36

时间限制 : 1 秒
内存限制 : 512 MB

【题目背景】 小x成为y县的新县长。y县下面有n个村,交通很不方便。正好小x准备设计一个项目给这些村之间修路。小x准备让地形较好的村尽量承担交通枢纽的功能,并且尽量减少计划的总费用,因此他规定了方案的得分规则:每个村都有一个地形评估分p_i,每修建一条从a村到b村的路,方案评估分就增加p_a+p_b。 要求在保证从任意村出发都能够通过新修的路能够到达任意其他村,并且方案的评估分尽可能的小。

【题目描述】 给定村子的数量n,每个村子用1-n编号。另外给定每个村子的地形评估分p,以及m条可以被修建的路。求在满足条件的情况方案的最小评估分。如果给定的路线图不能满足条件,则输出“ERROR”。

输入

从文件road.in中读入数据。输入第一行包含两个整数n,m。

第二行包含n个整数,表示每个村子的地形评估分,评分均在int范围之内(相加会超过int)。

从第三行到第m+2行,每行包含两个整数i,j ,表示从第i个村子到第j个村子可以修一条路。

输出

输出到文件road.out中。如果能够满足条件,则输出仅一个数字,表示最小的方案评估分。如果不能满足条件,则输出“ERROR”。

样例

输入

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

输出

15

输入

4 2
2 3 1 5
2 1
1 3

输出

ERROR