I got this question today In an qualifying round for a company SDE role. I wasn't able to solve the problem. Honestly, I would love if you could share some insight into the solution.

Initially I thought this is variation of Floyd Warshal problem, but could not come up with solution that can pass even a single test case.

Could you please suggest an appraoch on how should I go about solving this problem?

Problem Statement

There are N destinations holiday package organised by D2C tours and travels that Ben would like to visit during his India tour. Out of the N destination there are airports at only K of these destinations.

Due to covid, currently, there are only M one-way flights connecting these destinations. For each i (1 ≤ i ≤ M), Flight i travels from source Ui to destination Vi, at a cost of Ri rupees.

The airline authority received requests for Q one-way trips. For each i (1 ≤ i ≤ Q), the ith trip is from source Ai to destination Bi. In order to get from one location to another, the trip may include any sequence of direct flights, but it must include at least one airport (which may or may not be the start or the end). This requirement may result in, there being no valid route from Ai to Bi, considering the cost as 0. However, for all other trip requests, your goal is to help the authority determine the minimum cost of a valid tour.

Input Format

First line contains four space-separated integers numbers N, M, K, and Q.

Next M lines each contain three space-separated integers Xi, Yi and Ri.

Next Q lines each contain two space-separated integers Ai and Bi.

1 <= N <= 200
1 <= K <= min(100,N)
1 <= M, Q <= 10000
1 <= R[i] <= 10^9
1 <= X[i], Y[i], A[i], B[i] <= N

Output Format

The number of trips for which a valid route is possible and the minimum possible tour cost.

Sample Testcase #0

Testcase Input

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

Testcase Output

2 24
Explanation
The trip from 3->2 has only one possible route, of cost 10+7.

The trip from 2->3 has no valid route, since there is no flight leaving destination 2.

The trip from 1->2 has only one valid route again, of cost 7.

So the total cost of the route = 24 and there are 2 valid routes.