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.

Problem Description

在约会的过程中，网瘾少年决定和小女孩一起在理想国散步。

​ 理想国由 $n$ 个观景点和 $m$ 条有向道路组成。每条道路 $i$ 连接观景点 $u_i$ 到 $v_i$，行走这条路需要花费 $w_i$ 的时间。网瘾少年和小女孩目前的终点是理想国的中心广场 $S$。

​ 理想国有 $k$ 个著名的起始打卡点，网瘾少年可以带着小女孩从这 $k$ 个点中的任意一个出发前往终点 $S$。

​ 网瘾少年深知“陪伴是最长情的告白”。他希望他们在一起散步的时间尽可能地长。然而，他也不忍心让小女孩走冤枉路感到劳累，因此他向小女孩承诺：无论从哪个起点出发，他们走的一定是该起点到终点 $S$ 的最短路径。

​ 请你帮网瘾少年计算：在所有能够到达 $S$ 的起始打卡点中，选择哪一个起点出发，能让他们在“走最短路”的前提下，相处的时间最长？输出这个最长的时间

Input Format

第一行包含三个整数 $n, m, S$ ($1 \le n, m \le 2 \cdot 10^5, 1 \le S \le n$)，分别表示观景点的数量、道路的数量以及终点的编号。

​ 接下来 $m$ 行，每行包含三个整数 $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n, 1 \le w_i \le 10^9$)，表示有一条从 $u_i$ 到 $v_i$ 的单向道路，权值为 $w_i$。

​ 下一行包含一个整数 $k$ ($1 \le k \le n$)，表示起始打卡点的数量。

​ 最后一行包含 $k$ 个不同的整数 $P_1, P_2, \dots, P_k$ ($1 \le P_j \le n$)，表示这些打卡点的编号。

Output Format

输出一个整数。表示在所有可选起点中，到 $S$ 的最短路径长度的最大值。如果所有给定的打卡点都无法到达 $S$，请输出 $-1$。

Sample

样例 1

输入:

4 4 4
1 2 5
2 4 10
3 4 20
1 4 25
2
1 3

输出:

20

说明:

打卡点有两个：1 和 3。终点是 4。

• 从起点 1 到 4 的最短路：$1 \to 2 \to 4$，耗时 $5 + 10 = 15$。

• 从起点 3 到 4 的最短路：$3 \to 4$，耗时 $20$。

  最长的时间是 $20$。

样例 2

输入:

3 1 1
2 3 10
1
3

输出:

-1

Hint