开始: 2023-05-16 00:00:00

蒟蒻WKY的比赛

结束: 2023-05-18 12:30:00
当前  2025-06-06 11:58:20  类型: IOI  状态: 已经结束 

P1. 通信
描述

n 座保育区编号为 1,2,3 ... n,需要开始架设通信网线。

总共有 m 条线路可以进行连接,第 i 条线路连接第 u_i 座和第 v_i 座保育区。但是陆地上还是存在感染体,所以每条线路存在一个风险 d_i

另外赛利卡还给这些保育区下拨了 k 条卫星线路。第 i 条卫星线路可以将将第 c_i 座保育区连接到空中花园,而且因为是卫星线路,所以不存在风险。

赛利卡想知道,如果要使空中花园与任意一座保育区存在通信,那么所有需要架设的线路的风险值最小是多少(架设线路的总风险值)?

输入

第一行三个正整数 n, m, k

接下来的 m 行,每行三个正整数 u_i, v_i, d_i,如题意。

接下来的 k 行,每行一个正整数 c_i

输出

一行一个整数为最小的风险值。若无法使空中花园与任意一座保育区存在通信,输出 -1

样例

输入

3 3 2
1 2 3
1 3 2
2 3 1
1
2

输出

1
提示

对于100%的数据,保证 1≤n, m≤10^6

提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交