有n(n <= 500)个村庄,村庄之间有m条道路相连,现在需要给这些村庄供水,要求所有村庄都需要被供水。而给一个村庄供水有两种方式,一种方式是在该村庄打一口水井,另一种方式是在道路上连接水管到其他村庄,使得该村庄能直接或间接地连接到有水井的村庄。连接水管或打水井都有一定的花费,求能给所有村庄供水的最小花费。
输入的第一行为两个正整数n和m。
接下来m行,每行3个正整数a,b,c,以空格隔开,代表村庄a和村庄b之间有一条道路相连,在该道路连接水管的花费是c。村庄编号从1到n。
接下来一行,有n个正整数,以空格隔开,分别代表每个村庄打水井的花费。
输出一行,代表能给所有村庄都供水的最小花费。
请输入正确的证书编号
学员姓名:孙兴民
课程:Scratch Level 1
发证日期:2019.08.15