一家运输公司经常需要将货物从一个城市运送到另一个城市。该公司与一家连锁酒店达成了特殊协议，允许其司机免费入住该连锁酒店。司机每天最多只能驾驶 $10$ 小时。运输公司希望找到一条从起点城市到终点城市的路线，使得司机每天晚上都能住在该连锁酒店中的一家，并且从一个酒店到下一个酒店（或目的地）的驾驶时间不超过 $10$ 小时。当然，运送货物所需的天数也应尽可能少。

输入格式

输入文件包含多个测试用例。每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 10000$)，表示规划路线时考虑的城市数量。为简化起见，城市编号从 $1$ 到 $n$，其中 $1$ 是起点城市，$n$ 是终点城市。下一行包含一个整数 $h$，随后是 $c_1, c_2, \dots, c_h$，表示连锁酒店所在的城市编号。你可以假设 $0 \le h \le \min(n, 100)$。每个测试用例的第三行包含一个整数 $m$ ($1 \le m \le 10^5$)，表示规划路线时考虑的道路数量。接下来的 $m$ 行描述了这些道路。每条道路由 $3$ 个整数 $a, b, t$ ($1 \le a, b \le n$ 且 $1 \le t \le 600$) 描述，其中 $a$ 和 $b$ 是道路连接的两个城市，$t$ 是司机从道路一端行驶到另一端所需的时间（以分钟为单位）。输入以 $n = 0$ 结束。

输出格式

对于每个测试用例，输出一行，包含运输公司从城市 $1$ 到城市 $n$ 运送货物所需预订的最少酒店数量。如果无法找到一条满足司机每天驾驶时间不超过 $10$ 小时的路线，则输出 -1。

样例

样例输入 1

6
3 2 5 3
8
1 2 400
3 2 80
3 4 301
4 5 290
5 6 139
1 3 375
2 5 462
4 6 300
3
0
2
1 2 371
2 3 230
0

样例输出 1

2
-1