#P1669. Bakery
Bakery
题面翻译
玛莎想要开一家新的面包店,她希望在 个从 到 编号的城市中选择一个城市作为面包店的地址。在城市之间有 条双向道路,每一条双向道路都连接一对不同的城市,通过每条道路需要耗费一定的时间。
此外,玛莎还需要选择一个城市作为仓库,共有 个适合选择作为仓库的城市,这些城市的标号分别为 。
不幸的是,法律规定无法在能够被选择作为仓库的城市开设面包店,因此她只能在剩余的 个城市中选择面包店的地址。
现在,玛莎希望你能帮助她选择仓库以及面包店的地址,使得在仓库和面包店之间通行的耗时最小。
输入格式
输入的第一行包含三个整数 以及 ,分别表示城市数量,道路数量以及可被选作仓库的城市数量。
接下来 行,每行三个整数 ,描述一条在城市 和城市 之间的双向道路,通过这条道路将会耗费 的时间。
如果 ,那么最后一行将会包含 个不同的整数 ,表示可以被选择仓库城市的编号。如果 那么输入数据中就没有这一行。
输出格式
输出在最优的方案下,从仓库前往面包店的最小耗时。如果不存在一种这样的方案,则输出 。
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