Bovinia设计了连接N (1 < = N < = 20,000)个农场的航班。对于任何航班，指定了其中的k个农场作为枢纽。 (1 < = K <= 200 , K < = N)。

目前，共有M种单向航班（ 1 < = M < = 20,000 ），第i个航班从农场u_i至农场v_i花费d_i ( 1 < = d_i < =10,000 )美元。航班保证u_i或者v_i至少有一个是枢纽，任意两个农场至多只有一个航班，保证u_i≠v_i。

Bessie负责票务服务。共收到Q个度假请求，(1 < = Q < = 50,000)，其中第i个请求是从农场a_i至农场b_i 。请帮助她计算，每个请求是否满足 ，并计算：能满足的度假请求的最小费用总和。

 第1行：四个整数N,M,K,Q

 第2 - M+1行：三个整数ui,vi,di

 第M+2 - M+K+1行：枢纽的农场编号X (0<=X<=N)

 第M+K+2..M+K+Q+1：两个整数，度假请求ai,bi