不知道取什么名字的题目
题号：NC286107
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

\hspace{15pt}有 n 个岛 m 座桥，度过第 i 座桥需要耗费 w_i 的油，如果没有油就会开不动车。
\hspace{15pt}在这其中，有 k 个岛上有加油站，如果开车到达的岛上有加油站，就可以加满油。
\hspace{15pt}除此之外，还有 p 个传送门，传送门建在加油站之间，经过第 i 个传送门需要耗费 v_i 的油。
\hspace{15pt}现在，一共有 q 次询问，每次询问给出一个三元组 \{s,t,z\} ，代表询问油箱至少要多少容量（开始满油）才能在最多使用 z 次传送门情况下从 s 号岛到达 t 号岛，且至少经过一个加油站。

输入描述:

\hspace{15pt}第一行输入四个整数 n,m,k,p \left(1 \leq n,m \leq 5 \times 10^4;\ 1 \leq k \leq 100;\ 0 \leq p \leq 5 \times 10^4\right) 代表岛屿数量、桥数量、加油站数量、传送门数量。
\hspace{15pt}此后 m 行，第 i 行输入三个整数 u_i,v_i,w_i\left(1\leq u_i,v_i \leq n;\ u_i \neq v_i;\ 1\leq w_i \leq 10^6\right) 表示在 u_i 岛和 v_i 岛中有一个可以双向同行的桥，通过这个桥需要耗费 w_i 的油。
\hspace{15pt}第 m+2 行输入 k 个整数 b_1,b_2,\dots,b_k\left(1\leq b_i \leq n\right) 代表第 i 个加油站位于第 b_i 个岛屿，保证一个岛上最多一个加油站。
\hspace{15pt}此后 p 行，第 i 行输入三个整数 x_i,y_i,v_i\left(1\leq x_i,y_i \leq k;\ 1\leq v_i \leq 10^6\right) 表示从加油站 x_i 和加油站 y_i 之间有一个可以双向同行的传送门，通过这个传送门需要耗费 v_i 的油。
\hspace{15pt}第 m+p+3 行输入一个整数 q\left(1\leq q \leq 5000\right) 代表询问次数。
\hspace{15pt}此后 q 行，每行输入三个整数 s,t,z\left(1\leq s,t \leq n;\ 0\leq z \leq 10^5\right) 代表询问的三元组。

\hspace{15pt}除此之外，保证仅通过桥能够从任意一个岛屿到达任意一个岛屿；但可能存在多座桥、多个传送门连接同一对岛屿。

输出描述:

\hspace{15pt}对于每一次询问，在单独的一行上输出一个整数，代表最小的油箱容量，使得能在最多使用 z 次传送门的情况下从 s 到 t 且至少经过一个加油站。
示例1

输入

复制 
5 4 3 2
1 2 1
1 5 6
4 5 1
3 5 5
2 3 4
1 2 1
2 3 1
5
5 1 0
3 5 2
2 3 0
2 3 1
5 3 0

输出

复制 
7
1
8
1
5

说明

\hspace{15pt}对于这个样例，如下图所示，我们使用蓝色虚线代表传送门、蓝色斜体的圆圈代表加油站所在的岛屿。

\hspace{15pt}对于第一次询问，若要从 5 号岛屿到 1 号岛屿，不要忘记我们至少需要经过一个加油站，最佳的路径为 5 \to 1 \to {\color{#0288d1}{2}} \to 1 ，由于 2 号岛屿有加油站，所以我们的油箱只需要 7 的容量即可，我们可以在 2 号岛屿加满油，随后前往 1 号岛屿。
\hspace{15pt}对于第二次询问，最佳的路径为 {\color{#0288d1}{3 \to 4}} \to 5 。
\hspace{15pt}对于第三次询问，比较考验您的耐心，应当采取 {\color{#0288d1}{2}} \to 1 \to 5 \to {\color{#0288d1}{4}} \to 5 \to 3 的策略。
示例2

输入

复制 
5 9 2 5
1 5 1
5 4 5
4 2 2
2 3 1
2 3 3
2 3 5
4 5 4
1 2 1
2 3 5
3 4
1 2 2
1 2 3
1 2 4
1 2 4
1 2 1
5
2 3 0
1 3 0
2 3 1
2 2 1
1 2 1

输出

复制 
1
2
1
1
2

备注:

\hspace{15pt}您可能需要特别注意本题不同寻常的时间限制！