配点 : 525 点
問題文
在日本 N 有多个城市,并且城市双向相连。 M 有一条真正的路。城中之城 1 来自城市 它的编号最大为 N 。 i 真正的道路是城市 U_i 和城市 连接 V_i ,长度 C_i 这是一条公里长的路。除了公路之外,城市之间的旅行是不可能的。
另外, N 的城市 K 有一个现场表演场地。具体来说, k=1,2,\ldots,K 对抗城市 现场演出场地位于 A_k 。在这里,K 是 它仅由 4 凌驾于城市之上 1 和城市 连接 N 保证有现场演出场地。
人气偶像团体Bit♡Beat决定举办全国巡演。
全国巡演有所不同。 4 它将在三个城市的现场场地举行。另外,第一次live将在城市举行 1 ,最后一次直播是在城里 必须使用 N 来完成。 从
都市 1 开始 4 一城 1,N 在城市现场表演,包括 求到达 N 所需的最短距离。
但是,您在旅途中可能会多次访问同一城市。
制約
- 4\le N\le 10^5
- \displaystyle N-1 \le M\le \min\left(2\times 10^5, \frac{N(N-1)}2 \right)
- 1\le U_i < V_i \le N
- 1\le C_i \le 10^9
- 给定的图很简单且连通
- 4\le K\le N
- 1 = A_1 < A_2 < \ldots < A_K = N
- 所有输入值均为整数
入力
输入将以以下形式从标准输入给出。
N M K A_1 A_2 \ldots A_K U_1 V_1 C_1 U_2 V_2 C_2 \vdots U_M V_M C_M
出力
以公里为单位打印出您的答案。但是,不输出单位,而是将答案输出为整数。
入力例 1
5 4 4 1 2 4 5 1 3 1 2 3 10 3 4 100 4 5 1000
出力例 1
1121
通过如下移动 4 您可以在三个城市现场表演: 住在
- 都市 1 。
- 都市 1 来自城市 它的编号最大为 3 至 1 移动公里数。
- 都市 3 来自城市 它的编号最大为 2 至 10 移动公里数。
- 都市 2 。
- 都市 2 来自城市 它的编号最大为 3 至 10 移动公里数。
- 都市 3 来自城市 它的编号最大为 4 至 100 移动公里数。
- 都市 4 。
- 都市 4 来自城市 它的编号最大为 5 至 1000 移动公里数。
- 都市 5 。
在这种情况下行驶的距离是 1121 公里。
行驶距离为 1121 由于不可能移动不到一公里, 请输出 1121 。
入力例 2
6 11 4 1 4 5 6 1 2 40 2 3 30 3 6 20 1 4 100 2 4 80 3 4 60 4 6 40 1 5 80 2 5 70 3 5 60 5 6 50
出力例 2
210
入力例 3
15 22 5 1 5 11 13 15 1 2 668 1 6 869 2 3 633 2 7 563 3 4 32 3 8 158 4 5 314 4 9 859 5 10 935 6 7 826 6 11 167 7 8 112 7 12 606 8 9 279 8 13 731 9 10 181 9 14 442 10 15 557 11 12 499 12 13 174 13 14 791 14 15 477
出力例 3
2977