题目内容

供电区调度台把巡检车派到 N 个站点，站点编号从 1 到 N。车辆常驻枢纽站 $R$。值班手册规定：当天要按固定顺序走完 H 张工单，每张工单对应一个目标站点；车必须走当前最短耗时路线，且任意两站互相可达。

站间路网由 D 条单向线路和 U 条双向线路组成，走完第 $i$ 条线路耗时为 $c_i$。可能有重边与自环。

第 $i$ 张工单送达目标站 $z_i$ 后，先把「此前所有行驶与办理耗时，再加上本张工单的行驶耗时」记为 $T$。调度规则是：

全部工单办完后，车辆从最后一站沿最短路返回枢纽 $R$。求从出发到回到枢纽的总耗时。

约束：3 $\le$ N $\le$ 100000，0 $\le$ D $\le$ 200000，0 $\le$ U $\le$ 100000，1 $\le$ R $\le$ N，边权与办理耗时不超过 100000，1 $\le$ H $\le$ 10。

输入描述

第一行四个整数 N、D、U、R，表示站点数、单向线路数、双向线路数与枢纽编号（3 $\le$ N $\le$ 100000，0 $\le$ D $\le$ 200000，0 $\le$ U $\le$ 100000，1 $\le$ R $\le$ N）。

接下来 D 行，每行三个整数 $f_i,t_i,c_i$（1 $\le$ $f_i,t_i$ $\le$ N，0 $\le$ $c_i$ $\le$ 100000），表示一条单向线路。

接下来 U 行，每行三个整数 $f_j,t_j,c_j$（范围同上），表示一条双向线路。

接下来一行三个整数 P、Q、H（1 $\le$ P,Q $\le$ 100000，1 $\le$ H $\le$ 10），表示奇偶两种办理耗时与工单数。

最后一行 H 个整数 $z_1,z_2,\ldots,z_H$（1 $\le$ $z_i$ $\le$ N），表示工单目标站顺序。

输出描述

输出一个整数，表示办完所有工单并返回枢纽的总耗时。

样例1

输入

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

输出

11

说明

• 1→2 行驶 1，$T=1$ 为奇数，办理 3，累计 4。
• 2→4 行驶 2，$T=6$ 为偶数，办理 1，累计 7。
• 4→3 行驶 1，$T=8$ 为偶数，办理 1，累计 9。
• 返回 3→1 行驶 2，总耗时 11。

样例2

输入

3 0 3 2
1 2 2
2 3 2
3 1 2
5 4 2
3 3

输出

12

说明

• 2→3 行驶 2，$T=2$ 为偶数，办理 4，累计 6。
• 3→3 行驶 0，$T=6$ 为偶数，办理 4，累计 10。
• 返回 3→2 行驶 2，总耗时 12。