题目描述

有N(1 <= N <= 200)个农场，用1..N编号。航空公司计划在农场间建立航线。对于任意一条航线，选择农场1..K中的农场作为枢纽(1 <= K <= 100, K <= N)。

当前共有M (1 <= M <= 10,000)条单向航线连接这些农场，从农场u_i 到农场 v_i, 将花费 d_i美元。(1 <= d_i <= 1,000,000).

航空公司最近收到Q (1 <= Q <= 10,000)个单向航行请求。第i个航行请求是从农场a_i到农场 b_i，航行必须经过至少一个枢纽农场（可以是起点或者终点农场），因此可能会多次经过某些农场。

请计算可行航行请求的数量，及完成所有可行请求的总费用。

输入格式

• 第 1 行：四个整数 $N, M, K, Q$。
• 第 $2 \dots 1+M$ 行：第 $i+1$ 行包含航线 $i$ 的三个参数 $u_i, v_i, d_i$，分别对应航线的起点、终点和通行费用。
• 第 $2+M \dots 1+M+Q$ 行：第 $1+M+i$ 行包含第 $i$ 次航行请求的两个参数 $a_i, b_i$，分别对应航行的起点和终点。

输出格式

• 第 1 行：$Q$ 个请求中，存在合法航行路径的请求总数量。
• 第 2 行：所有合法请求对应的最小航行费用的总和。

3 3 1 3 
3 1 10 
1 3 10 
1 2 7 
3 2 
2 3 
1 2 

2 
24 

提示

样例中共有3个农场，农场1是唯一的枢纽。存在三条航线：从农场3到农场1费用10，从农场1到农场3费用10，从农场1到农场2费用7。三个航行请求分别是3→2、2→3、1→2：

• 3→2的合法路径为3→1→2，总费用10+7=17
• 2→3不存在合法路径，没有从农场2出发的航线
• 1→2本身起点就是枢纽，直接通行费用为7 最终统计得到2个合法请求，总费用17+7=24。