题目描述

某地区有 $n$ 个站点和 $m$ 条双向道路。第 $i$ 条道路连接 $u_i,v_i$，通过这条道路需要 $w_i$ 个单位时间。

巡检车从站点 $1$ 出发，最终必须到达站点 $n$。另外有 $k$ 个重点站点 $p_1,p_2,\ldots,p_k$，巡检过程中必须至少经过每个重点站点一次。

道路和站点都可以重复经过，重点站点的访问顺序由你决定。

求从 $1$ 出发、经过所有重点站点并最终到达 $n$ 的最短总时间。如果不存在这样的路线，输出 -1。

输入格式

第一行三个整数 $n,m,k$。

第二行 $k$ 个互不相同的整数 $p_1,p_2,\ldots,p_k$。当 $k=0$ 时，该行为空行。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示一条双向道路。

保证重点站点均不等于 $1$ 或 $n$。

输出格式

输出一个整数表示最短总时间；如果无解，输出 -1。

样例

6 7 2
3 5
1 2 2
2 3 2
3 6 5
1 4 3
4 5 2
5 6 2
3 5 1

7

数据范围

• $2\le n\le 10^5$；
• $0\le m\le 2\times10^5$；
• $0\le k\le 12$；
• $1\le w_i\le 10^9$。