← 返回题目列表

Codeforces · 196/E

E. 打开门户

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

帕维尔玩一个著名的电脑游戏。玩家负责整个国家,他可以自由旅行,完成任务并获得经验。

这个国家有 n 个城市,由 m 条不同长度的双向道路连接,因此可以从任何一个城市到达任何另一个城市。其中 k 个城市设有传送门。游戏开始时所有传送门均关闭。当玩家访问传送门城市时,传送门就会打开。奇怪的是,一个人可以从一个开放的门户瞬移到另一个开放的门户。传送不需要时间,这使得玩家能够在该国相当偏远的地区之间快速旅行。

游戏开始时,帕维尔位于 1 号城市。他想尽快打开所有传送门。他需要多少时间才能做到这一点?

输入

第一行包含两个空格分隔的整数 n 和 m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105),显示游戏中有多少个城市和道路。

接下来的 m 行中的每一行都包含对一条道路的描述,三个空格分隔的整数 xi, yi, wi (1 ≤ xi, yi ≤ n, xi ≠ yi, 1 ≤ wi ≤ 109) — 第 i 条道路连接的城市数量以及通过该道路从一个城市到另一个城市所需的时间。任意两个城市仅由不超过一条道路连接。我们保证可以沿着该国的道路从任何一个城市到达任何另一个城市。

下一行包含整数 k (1 ≤ k ≤ n) — 门户的数量。

下一行包含 k 个空格分隔的整数 p1, p2, ..., pk — 已安装门户的城市编号。每个城市最多只有一个门户。

输出

打印一个数字——玩家打开所有传送门所需的最短时间。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

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

输出 #1

2

输入 #2

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

输出 #2

16

输入 #3

4 3
1 2 1000000000
2 3 1000000000
3 4 1000000000
4
1 2 3 4

输出 #3

3000000000

注意

在第二个示例中,玩家必须来到城市 2,在那里打开一个传送门,然后前往城市 3,在那里打开一个传送门,传送回城市 2,最后在城市 4 完成旅程。