← 返回题目列表

Codeforces · 707/B

B. 面包店

中文机器翻译题面 查看原题

玛莎想在编号为 1 到 n 的 n 个城市之一开设自己的面包店并烘烤松饼。有 m 条双向道路,每条道路连接一对城市。

为了在她的面包店烘烤松饼,玛莎需要从一些仓库建立面粉供应。只有k个仓库,位于不同的城市,编号为a1,a2,...,ak。

不幸的是,玛莎所居住的国家的法律禁止在任何拥有仓库的城市开设面包店。她只能在另外 n - k 个城市中开设它,当然,面粉运输应该付费 - 仓库和面包店之间每公里玛莎应该支付 1 卢布。

正式来说,如果玛莎在某个城市 b(对于每个 1 ≤ i ≤ k,ai ≠ b)开设面包店,并在某个城市 s(对于某些 1 ≤ j ≤ k,s = aj)选择一个仓库,并且 b 和 s 通过总长度为 x 的道路路径连接(如果有多个路径,玛莎能够选择应使用哪一条),则玛莎将支付 x 卢布。

玛莎非常节俭和理性。她对一个城市感兴趣,在那里她可以开设她的面包店(并选择 k 个仓库之一以及有面包店的城市和有仓库的城市之间的路径之一)并支付尽可能少的卢布来运送面粉。请帮助玛莎找到这个金额。

输入

输入的第一行包含三个整数 n、m 和 k (1 ≤ n, m ≤ 105, 0 ≤ k ≤ n)——分别是 Masha 居住的国家的城市数量、城市之间的道路数量以及面粉仓库数量。

接下来是 m 行。它们每个都包含三个整数 u、v 和 l (1 ≤ u, v ≤ n, 1 ≤ l ≤ 109, u ≠ v),这意味着城市 u 和 v 之间有一条长度为 l 公里的道路。

如果 k > 0,则输入的最后一行包含 k 个不同的整数 a1, a2, ..., ak (1 ≤ ai ≤ n) - 拥有面粉仓库的城市数量。如果 k = 0,则输入中不会显示此行。

输出

在唯一的一行中打印玛莎应支付的面粉运输的最低卢布金额。

如果面包店在n个城市中的任何一个都无法开业(同时满足条件),则在唯一的行中打印-1。

示例

输入 #1

5 4 2
1 2 5
1 2 3
2 3 4
1 4 10
1 5

输出 #1

3

输入 #2

3 1 1
1 2 3
3

输出 #2

-1

注意

图像展示了第一个示例案例。拥有存储设施的城市和代表答案的道路都变暗了。