Air Bovinia Ticketing

Air Bovinia operates flights connecting N farms. Among these, the farms numbered 1 through K are designated as hubs. The airline runs M one‐way flights. Each flight goes from a farm u_i to a farm v_i with cost d_i dollars, and for every flight at least one of u_i and v_i is a hub. There is at most one flight in any given direction between two farms, and no flight begins and ends at the same farm.

There are Q travel requests asking to go from farm a_i to farm b_i. A travel request can only be fulfilled if there exists a route from a_i to b_i which visits at least one hub (i.e. a farm with index between 1 and K). If possible, the ticket is sold at the minimum cost of such a route.

Your task is to compute, among the Q requests, the total number of possible tickets as well as the sum of the minimum costs (note that the cost might not fit in a 32-bit integer).

The key observation is that if a valid route exists from a to b passing some hub h, then its cost is
\( d(a, h)+d(h, b) \), where
\( d(x, y) \) is the shortest path distance from x to y in the flight network. Thus, for each query, the answer is given by
\( \min_{1 \le h \le K} \bigl(d(a, h)+d(h, b)\bigr) \).

inputFormat

outputFormat

sample

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

2 23