2599 - 最短路径
描述

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

输入

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

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

接下来 k 行每行个整数表示标记点编号。


输出

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


样例

输入

3 3 2 1 1
1 2 1
2 3 1
3 1 1
2
3

输出

3
提示

对于 100% 的数据,1≤n≤50000,m≤1000000,k≤10,1≤z≤5000

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过次数 0