#P1669. Bakery

Bakery

题面翻译

玛莎想要开一家新的面包店,她希望在 nn 个从 11nn 编号的城市中选择一个城市作为面包店的地址。在城市之间有 mm 条双向道路,每一条双向道路都连接一对不同的城市,通过每条道路需要耗费一定的时间。

此外,玛莎还需要选择一个城市作为仓库,共有 kk 个适合选择作为仓库的城市,这些城市的标号分别为 a1,a2,...,aka_1, a_2, ..., a_k

不幸的是,法律规定无法在能够被选择作为仓库的城市开设面包店,因此她只能在剩余的 nkn - k 个城市中选择面包店的地址。

现在,玛莎希望你能帮助她选择仓库以及面包店的地址,使得在仓库和面包店之间通行的耗时最小。

输入格式

输入的第一行包含三个整数 n,mn, m 以及 k (1n,m105,0kn)k\ (1 ≤ n, m ≤ 10^5, 0 ≤ k ≤ n),分别表示城市数量,道路数量以及可被选作仓库的城市数量。

接下来 mm 行,每行三个整数 u,v,l (1u,vn,1l109,uv)u, v, l\ (1 ≤ u, v ≤ n, 1 ≤ l ≤ 10^9, u ≠ v),描述一条在城市 uu 和城市 vv 之间的双向道路,通过这条道路将会耗费 ll 的时间。

如果 k>0k > 0,那么最后一行将会包含 kk 个不同的整数 a1,a2,...,ak (1ain)a_1, a_2, ..., a_k\ (1 ≤ a_i ≤ n),表示可以被选择仓库城市的编号。如果 k=0k = 0 那么输入数据中就没有这一行。

输出格式

输出在最优的方案下,从仓库前往面包店的最小耗时。如果不存在一种这样的方案,则输出 1-1

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