Minimum Cost to Reach Destination in Time

The first line of input contains three space-separated integers: n (number of cities), E (number of edges), and maxTime.

The second line contains 'n' space-separated integers, representing the passingFees array.

The next 'E' lines each contain three space-separated integers: u, v, and time.

Print a single integer representing the minimum cost of a valid journey.

If no valid journey exists, print -1.

This problem is a variation of the shortest path problem. A standard algorithm like Dijkstra's must be modified.

The state in our search cannot just be the current city. We need to track the minimum time to reach each city.

A priority queue should be used, but it should prioritize states with the minimum cost, as that is what we want to optimize. The state in the queue would be (current_cost, current_time, current_city).

An auxiliary array, min_time[city], is needed to keep track of the minimum time found so far to reach each city. This helps prune paths that are both slower and more expensive.

Sample Input 1:

6 6 30
5 1 2 20 20 3
0 1 10
1 2 10
2 5 10
0 3 1
3 4 10
4 5 15

Sample Output 1:

11

Explanation for Sample 1:

There are two main paths from city 0 to 5:
Path 1: `0 -> 1 -> 2 -> 5`.
- Time: 10 + 10 + 10 = 30. This is `<= maxTime`.
- Cost (fees): `5 (city 0) + 1 (city 1) + 2 (city 2) + 3 (city 5) = 11`.
Path 2: `0 -> 3 -> 4 -> 5`.
- Time: 1 + 10 + 15 = 26. This is `<= maxTime`.
- Cost (fees): `5 (city 0) + 20 (city 3) + 20 (city 4) + 3 (city 5) = 48`.
The minimum cost among valid paths is 11.

Sample Input 2:

6 6 29
5 1 2 20 20 3
0 1 10
1 2 10
2 5 10
0 3 1
3 4 10
4 5 15

Sample Output 2:

48

Explanation for Sample 2:

Path `0 -> 1 -> 2 -> 5` takes 30 minutes, which is greater than `maxTime` (29). This path is invalid.
Path `0 -> 3 -> 4 -> 5` takes 26 minutes, which is valid. Its cost is 48.
This is the only valid path, so the minimum cost is 48.

Expected Time Complexity:

The expected time complexity is O(E log V), where V is the number of cities and E is the number of edges.

Constraints:

1 <= maxTime <= 1000
n == passingFees.length
2 <= n <= 1000
n - 1 <= E <= 1000
0 <= u, v < n
1 <= time <= 1000
1 <= fees <= 1000

Time limit: 1 sec