题目描述

某服务器的交通系统可以概括为 $n$ 个节点。

在主世界有 $m$ 条冰道，第 $i$ 条冰道连接 $u_i$ 和 $v_i$，通过需要 $w_i$ 分钟（$1 \le i \le m$）。

在下界也有 $d$ 条铁路，第 $j$ 条铁路连接 $x_j$ 和 $y_j$，通过需要 $z_j$ 分钟（$1 \le j \le d$）。

同时，还设有 $p$ 个传送门，连接节点 $h_k$ 的主世界和节点 $h_k$ 的下界，通过需要 $1$ 分钟（$1 \le k \le p$，$1 \le h_k \le n$）

现在有一玩家想从节点 $s$ 的主世界去往节点 $t$ 的主世界，他想知道自己最少要花多少分钟？

输入格式

输入格式如下：

n m d p s t
u_1 v_1 w_1
...
u_m v_m w_m
x_1 y_1 z_1
...
x_d y_d z_d
h_1 h_2 ... h_p

输出格式

一行一个整数，表示答案。

3 2 2 2 1 3
1 2 100
2 3 100
1 2 1
2 3 1
1 3

4

12 11 11 4 1 3
1 2 100
2 3 150
3 4 200
4 5 10
5 6 20
6 7 15
7 8 25
8 9 120
9 10 130
10 11 140
11 12 160
1 2 5
2 3 8
3 4 3
4 5 100
5 6 110
6 7 105
7 8 95
8 9 4
9 10 6
10 11 7
11 12 2
1 4 8 12

218

数据范围与约定

$1 \le n,m,d,p \le 10^5$

$0 \le w_i,z_j \le 10^9$

数据保证有解。*