有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，航行必须经过至少一个枢纽农场（可以是起点或者终点农场），因此可能会多次经过某些农场。
请计算可行航行请求的数量，及完成所有可行请求的总费用。
第一行:四个整数: N, M, K, Q.
第二行到第M+1行: 每行第条航线 u_i, v_i, d_i
接下来每行:第i个请求的a_i 和 b_i
第一行： 可行航行请求的数量
第二行:
所有可行请求的总费用的最小值
3 3 1 3
3 1 10
1 3 10
1 2 7
3 2
2 3
1 2
2
24