供水问题

题目内容

题目描述

有n(n <= 500)个村庄,村庄之间有m条道路相连,现在需要给这些村庄供水,要求所有村庄都需要被供水。而给一个村庄供水有两种方式,一种方式是在该村庄打一口水井,另一种方式是在道路上连接水管到其他村庄,使得该村庄能直接或间接地连接到有水井的村庄。连接水管或打水井都有一定的花费,求能给所有村庄供水的最小花费。

输入描述

输入的第一行为两个正整数n和m。

接下来m行,每行3个正整数a,b,c,以空格隔开,代表村庄a和村庄b之间有一条道路相连,在该道路连接水管的花费是c。村庄编号从1到n。

接下来一行,有n个正整数,以空格隔开,分别代表每个村庄打水井的花费。

输出描述

输出一行,代表能给所有村庄都供水的最小花费。

样例输入

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

样例输出

12

提示

提交评测
请登录后再操作

题目描述

供水问题
1176
0
Level3
25
16
64%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在