Vacation Planning

Air Bovinia connects the $N$ farms where the cows live. The farms are numbered $1$ through $N$, and farms $1$ through $K$ are hubs.

The airline currently runs $M$ one-way flights. Flight $i$ goes from farm $u_i$ to farm $v_i$ and costs $d_i$ dollars.

Air Bovinia has taken $Q$ requests for one-way trips. Trip $i$ starts at farm $a_i$ and ends at farm $b_i$. A route is any sequence of direct flights and may visit the same farm several times, but it has to include at least one hub. A hub at the start or at the destination satisfies that requirement. When the start and the destination are the same farm, the route that takes no flight at all counts as a route, and it satisfies the requirement only if that farm is a hub.

Because of this requirement, a trip from $a_i$ to $b_i$ may have no route at all. For every trip that does have one, find the minimum cost.

$1 \le N \le 200$, $1 \le K \le 100$, $K \le N$, $1 \le M \le 10\,000$, $1 \le d_i \le 1\,000\,000$, and $1 \le Q \le 10\,000$. Several flights may connect the same pair of farms, and a flight may start and end at the same farm.

• The first line contains $N$, $M$, $K$, and $Q$.
• Line $i$ of the next $M$ lines contains $u_i$, $v_i$, and $d_i$ for flight $i$.
• Line $i$ of the next $Q$ lines contains $a_i$ and $b_i$ for trip $i$.

• On the first line, print how many trips have a valid route.
• On the second line, print the sum of the minimum costs of those trips. Print $0$ when no trip has a valid route.

The example input has three farms, and farm $1$ is the hub. A flight runs from farm $3$ to farm $1$ for $10$ dollars, and the other flights read the same way.

The cheapest route from farm $3$ to farm $2$ passes through farm $1$ and costs $10 + 7 = 17$. No flight leaves farm $2$, so the trip from farm $2$ to farm $3$ has no route. The trip from farm $1$ to farm $2$ has a single route, costing $7$.