题目描述

$\red{Bovinia}$航空公司的航线连接了奶牛居住的$\red{N}$个农场$\red{(1<=N<=20000)}$。如同其他公司一样，所有农场当中的$\red{K}$个被设定为枢纽。

现在$\red{Bovinia}$航空公司提供$\red{M}$条单项航线$\red{(1<=M<=20000)，}$第$\red{i}$条航线从$\red{u_i}$号农场出发，目的地是第$\red{v_i}$号农场，开销为$\red{k_i}$美刀。$\red{(1<=k_i<=10000)}$

对于每一条航线，$\red{u_i}$和$\red{v_i}$当中至少有一个是枢纽，两个农场间的航线最多只有$\red{1}$条，没有起点终点相同的航线。

$\red{Bessie}$负责管理$\red{Bovinia}$航空公司的售票服务。不幸的是，

当她离开了几个小时去吃一些美味的干草时，奶牛们发来了

$\red{Q(1<=Q<=50000)}$个单程的假期旅行订单，$\red{i}$号订单希望从$\red{a_i}$号农场飞到$\red{b_i}$号农场。

$\red{Bessie}$快要被订票的工作压垮了，请你帮帮她计算一下每个订单能否被满足，如果能满足，

计算满足该订单的最小花费。

为了减少输出量，你应当只输出最多可满足的订单数和最小的总花费。

为了减少输出大小，您应该只输出可能的票据请求总数，以及它们的最小总成本。注意，这个数字可能不适合$\red{32}$位整数。

是$\red{n}$个点$\red{m}$条有向边，求两两之间的最短路，要求路径上必须经过编号$\red{1\sim}$$\red{k}$的至少一个点

输入格式

第$\red{1}$行:整数$\red{N}$、$\red{M}$、$\red{K}$和$\red{Q}$。

第$\red{2 . .M +1}$:第$\red{i+1}$行包含$\red{u_i}$、$\red{v_i}$和$\red{d_i}$。$\red{(1 <= u_i, v_i <= N, u_i != v_i)}$

第$\red{M + 2..M + K + 1}$行:每一行包含一个集线器的（范围）

第$\red{M + K + 2..M + K + Q + 1}$行:每行两个数字，表示请求从农场$\red{a_i}$到$\red{b_i}$的票。$\red{(1 <= a_i, b_i <= N, a_i != b_i)}$

输出格式

第$\red{1}$行:整数$\red{N}$、$\red{M}$、$\red{K}$和$\red{Q}$。

第$\red{2 . .M +1}$行:第$\red{i+1}$行包含$\red{u_i}$、$\red{v_i}$和$\red{d_i}$。$\red{(1 <= u_i, v_i <= N, u_i != v_i)}$

第$\red{M + 2..M + K + }$行:每一行包含一个集线器的（范围）

第$\red{M + K + 2..M + K + Q + 1}$行:每行两个数字，表示请求从农场$\red{a_i}$到$\red{b_i}$的票。$\red{(1 <= a_i, b_i <= N, a_i != b_i)}$

样例

输入样例

3 3 1 2
1 2 10
2 3 10
2 1 5
2
1 3
3 1

输出样例

1
20