Start: 2023-05-16 00:00:00

蒟蒻WKY的比赛

End: 2023-05-18 12:30:00
Now  2026-06-17 14:20:25  类型: IOI  状态: Ended 

P1. 通信
Description

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

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

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

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

Input

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

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

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

Output

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

Examples

Input

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

Output

1
Hint

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

Submit

题目参数
Time Limit 1 second
Memory Limit 128 MB
Submit