题目背景

Nilan 是 Berapur 国家的一位马拉松组织者。他计划在国家内的城市网络中组织一场接力马拉松。

题目描述

该国家共有 $N$ 个城市，通过 $M$ 条双向道路连接。每个城市编号为 $1$ 到 $N$，每条道路编号为 $1$ 到 $M$，第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，通行时间为 $w_i$ 秒。道路网络中没有自环或重复边。

在 $N$ 个城市中，有 $K$ 个特殊城市，编号分别为 $A_1, A_2, \dots, A_K$。

接力马拉松的规则如下：

1. 两组人分别从两个起始城市 start1 和 start2 出发；
2. 第一组人从 start1 前往 finish1；
3. 第一组人到达 finish1 后，第二组人立即（无延迟）从 start2 前往 finish2；
4. 接力马拉松在第二组人到达 finish2 时结束。

接力马拉松的有效条件：

• start1、finish1、start2 和 finish2 必须是四个不同的特殊城市。

令 $D(a, b)$ 表示从城市 $a$ 到城市 $b$ 的最短通行时间。如果 $a$ 和 $b$ 之间无路径，则定义 $D(a, b) = \infty$。

接力马拉松的总耗时定义为：

$$D(start1, finish1) + D(start2, finish2)$$

你的任务是找到所有有效的起点和终点组合中，总耗时的最小值。

输入格式

• 第一行包含三个整数 $N, M, K$，分别表示城市数量、道路数量和特殊城市数量。
• 接下来 $M$ 行，每行包含三个整数 $u_i, v_i, w_i$，表示城市 $u_i$ 和 $v_i$ 之间有一条通行时间为 $w_i$ 秒的道路。
• 最后一行包含 $K$ 个整数 $A_1, A_2, \dots, A_K$，表示特殊城市的编号。

输出格式

输出一个整数，表示接力马拉松的最小总耗时。

5 4 4
1 2 1
3 4 2
4 5 5
5 3 8
3 1 5 2

8

6 6 4
1 2 5
2 4 7
4 6 50
6 5 3
1 5 15
3 5 6
1 5 4 6

15

提示

【样例解释】

对于样例 #1：

• 有效组合为 start1 = 1, finish1 = 2, start2 = 3, finish2 = 5；
• $D(1, 2) = 1$，$D(3, 5) = 7$；
• 总耗时为 $1 + 7 = 8$。

对于样例 #2：

• 有效组合为 start1 = 1, finish1 = 4, start2 = 5, finish2 = 6；
• $D(1, 4) = 12$，$D(5, 6) = 3$；
• 总耗时为 $12 + 3 = 15$。

【数据范围】

• $4 \leq K \leq N \leq 10^5$
• $2 \leq M \leq \min \left( \frac{N(N-1)}{2}, 3 \times 10^6 \right)$
• $1 \leq w_i \leq 1000$
• $1 \leq u_i \neq v_i \leq N$

子任务编号	分值	限制条件
$1$	$5$	$4 \leq K \leq N \leq 50$
$2$	$12$	$4 \leq K \leq N \leq 500$
$3$	$25$	城市 $1$ 和城市 $2$ 是特殊城市，直接由一条耗时为 $1$ 秒的道路相连，且城市 $1$ 不与其他城市相连，城市 $2$ 也不与其他城市相连
$4$	$58$	无额外限制