#2691. 最短路

最短路

题目描述

给定一个n\red{n}个点m\red{m}条边的有向图,有k\red{k}个标记点,要求从规定的起点按任意顺序经过所有标记点到达规定的终点,问最短的距离是多少。

输入格式

第一行5\red{5}个整数n\red{n}m\red{m}k\red{k}s\red{s}t\red{t,}表示点个数、边条数、标记点个数、起点编号、终点编号。

接下来m\red{m}行每行3\red{3}个整数x\red{x}y\red{y}z\red{z,}表示有一条从x\red{x}y\red{y}的长为z\red{z}的有向边。

接下来k\red{k}行每行一个整数表示标记点编号。

输出格式

输出一个整数,表示最短距离,若没有方案可行输出1\red{-1}

样例

输入样例

3 3 2 1 1

1 2 1

2 3 1

3 1 1

2

3

输出样例

3

提示

样例解释

路径为1>2>3>1\red{1->2->3->1}

数据

20%\red{20\%}的数据n<=10\red{n<=10}

50%\red{50\%}的数据n<=1000\red{n<=1000}

另有20%\red{20\%}的数据k=0\red{k=0}

100%\red{100\%}的数据n<=50000\red{n<=50000,}m<=100000\red{m<=100000,}0<=k<=10\red{0<=k<=10,}1<=z<=5000\red{1<=z<=5000}