题目描述Description

SNTU是一个很大的学校，为了方便同学出行，学校内设置了很多走廊连接各个建筑物，学生们可以通过走廊高效地出行。但是随着走廊服役时间的增加，走廊上的问题越来越多，所以学校不得不把出问题的地方封起来进行维修。DOGGOD_Q 最近非常苦恼，因为最近他去教学楼的一条要道被封住了，所以他不得不绕路经过其他地方，因此迟到了好几次。现在他把学校走廊的设置情况告诉了你，并告诉你他绕路后必须经过的几个地方，请你帮他找出去教学楼的最短路径。

输入格式Input

输入数据的第一行为四个正整数 n (2 \leq n \leq 500), m (n-1 \leq m \leq n * n), k (0 \leq k \leq n) 表示学校内有 n 个建筑物，m 条走廊，维修时 DOGGOD_Q 想要上学必须依次经过 k 个建筑物。数据保证各个建筑物之间都是连通的，并且每两个建筑物之间最多只有一条走廊

接下来 m 行每行有三个整数 x, y, w (1 \leq x, y \leq n) (0 \leq w \leq 1e5) 表示建筑物 x 和建筑物 y 之间有一条长度为 w 的走廊

再接下来 k 行每行有一个正整数 v，表示 DOGGOD_Q 必须经过建筑物 v。输入的 k 个建筑物必须依次经过。DOGGOD_Q 的起点为 1 号建筑物，目标教学楼为 n 号建筑物。数据保证一定存在合法路径。

输出格式Output

输出一行，为一个整数，代表当前 DOGGOD_Q 去教学楼的最短路径。

样例Sample

出题Author

DOGGOD_Q

来源Source