题目描述

众所周知，新世纪的科学很发达，于是 Ray 和 Raven 开始了星际探险，他们在宇宙中开辟了一片空间，建造了 $n$ 个空间站。这 $n$ 个空间站由一些单向的时空隧道连接，这些时空隧道都有一个穿越指数，穿过这些时空隧道，你可以走到未来或者回到过去，当然，这些都是由穿越指数决定的。有一天，Ray 和 Raven 开始了一场比赛。他们要从一个空间站 $s$ 出发去另一个空间站 $t$，先到的人获胜。Raven 一定会选一条能最快到达 $t$ 的路线。他希望 Ray 输给他，所以事先在 Ray 的飞船上设定了飞行路径，使得 Ray 从 $s$ 到 $t$ 只能走一条特定的路径。

但是，Ray 有对策，他有一台能够操纵时空隧道的机器，这台机器每次可以把某一条时空隧道的穿越指数增加或减少 $1$，但是因为操纵机器很累，所以 Ray 希望尽可能少改动，当然，如果改动后从某个空间站经过一系列的穿越可以在从这个空间站出发之前回到这个空间站，那么这样的改动是不允许的。修改之后，Raven 依然会走能最快到达终点的路线，所以 Ray 是不可能赢的。但他请你帮助他确定改动时空隧道的方案，使得他能和 Raven 同时到达 $t$。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，代表空间站的数目和时空隧道的数目。

接下来 $m$ 行，每行三个整数 $u,v$ 和 $w$，代表从空间站 $u$ 到空间站 $v$ 有一条时空隧道，它的穿越指数是 $w$。空间站的编号是 $0\sim n − 1$。

第 $m + 2$ 行包含一个整数 $p$，代表 Raven 在 Ray 的飞船上设定的那条路径的空间站数。

第 $m + 3$ 行包含 $p$ 个互不相同的数，表示那条路径上的空间站的编号，第一个数是 $s$，最后一个数是 $t$。

输出格式

输出的第一行包含一个整数，表示 Ray 走那条路径并且能够赢得比赛的情况下操纵时间机器的最小次数。

样例输入

3 3
0 1 1
1 2 2
0 2 1
3
0 1 2

样例输出

2

数据规模与约定

一共有 10 个数据，对于第 $i(1\leq i\leq 10)$ 个数据，$n=i\times 500$，$m=i\times 5\times 10^3$。

对于所有数据，均有 $0\leq w\leq 2\times 10^3$，$1\leq p\leq n$。