时空限制

1S/512M

题目描述

给定由 $n$ 个点和 $m$ 条有向边组成的有向图。

有 $k$ 个地点要去，请你规划一条从点 $1$ 出发，以任意顺序经过所有 $k$ 个点后，再回到点 $1$ 的最短路线。

允许重复多次经过同一条边或同一个点。

格式

输入格式

第一行包含三个整数 $n,m,k$，分别表示点的数量，边的数量，和需要经过的点的数量。

第二行包含 $k$ 个整数 $a_i$，分别表示 $k$ 个需要经过的点的编号。

接下来 $m$ 行每行包含三个整数 $u_i,v_i,w_i$，表示一条起点为 $u_i$ ，终点为 $v_i$ ，长度为 $w_i$ 的有向边。

输出格式

输出一个整数表示最短路线的长度。无解输出 $-1$。

样例

样例输入 #1

4 6 2
2 4
1 2 1
2 3 3
3 4 1
4 2 2
2 3 6
3 1 1

样例输出 #1

11

数据规模

对于 $100\%$ 的数据， $1\leq n\leq 10^5$， $1\leq m \leq 2\times 10^5$， $1\leq k \leq \min(10,n)$， $2\leq a_i \leq n$， $1\leq u_i,v_i \leq n$， $1\leq w_i \leq 10^9$。数据保证 $a_i$ 两两不同。