You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

棋城逃离，要塞追击。

题目背景

省常中的快乐集训开始啦啦啦啦！

张家豪在玩游戏写代码的快乐时光仍频出金句：“潘睿真蠢。”

好脾气的潘睿当然不会生气了，拿着钻石剑就奔着张家豪去了。

“伟大的一看就很聪明的添柴少年”张家豪肯定不会待在原地等着潘睿，他立刻在整张游戏地图中绕起了圈。

潘睿通过刘弈钦的帮助，知道了张家豪的行动路线。现在在一旁的王晓睿想知道潘睿最少要多久才能抓住张家豪。

题目描述

整张游戏地图被分成了 $N$ 块大陆，编号为 $1\sim N$。大陆之间被张家豪用“贯穿南北的大铁路”连接，因为张家豪认为世界万物都应确定，所以大铁路是单行道。

现在给出张家豪与潘睿的出生点与张家豪的行动路线（如果不被抓住就会一直跑下去,直到跑到最后一个大陆或下一个计划经过的大陆无法直接到达），请你求出潘睿要多久才能抓住张家豪。潘睿是大聪明，他不一定要一直跑，可以停在原地等张家豪撞上门来。

输入格式

第 $1$ 行输入两个正整数 $N,M$。分别代表大陆的数量与大铁路的数量

第 $2\sim M+1$ 行，每行输入三个正整数 $u,v,w$，表示某条大铁路是从 $u$ 大陆至 $v$ 大陆的单行道，通过这条路二人均需 $w$ 单位的时间。

第 $M+2$ 行，输入一个正整数 $T$，表示张家豪的逃跑路线

第 $M+3$ 行，输入 $T$ 个正整数 $a_1,a_2,a_3,\cdots,a_T$，表示张家豪会以 $a_1\to a_2\to a_3\to\cdots\to a_T$ 的顺序在各个大陆上逃跑。

第 $M+4$ 行，输入两个正整数 $sp_p,sp_z$，表示潘睿的出生点与张家豪的出生点。

输出格式

一行一个正整数，为潘睿追到张家豪的最少时间

如果怎么也追不上，输出 -1。

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

11

提示

$1\le N,M,T \le 10^5,1\le a_i,u,v,sp_p,sp_z\le N,1\le w \le 10^3,a_1=sp_z$。

另外对于 $\forall u,v$，保证 $u\neq v$。