There is a country with n cities labeled from $0$ to n $- 1$. The country has bidirectional roads represented by an array edges, where edges[i] = $[x_i, y_i, {time}_i]$ denotes a road connecting city $x_i$ and city $y_i$ that requires ${time}_i$ minutes to traverse.

You are given an integer array passingFees of length n, where passingFees[j] is the fee required to visit city $j$, and an integer maxTime.

You start at city $0$ and wish to reach city n $- 1$. The total cost of a path is the sum of the passing fees for all cities visited along the route, including city $0$ and city n $- 1$.

Return the minimum cost to travel from city $0$ to city n $- 1$ such that the total travel time is at most maxTime. If no such route exists within the given time limit, return $-1$.

Constraints:

• $1 \leq$ maxTime $\leq 1000$

• n $==$ passingFees.length

• $2 \leq$ n $\leq 1000$

• n $- 1 \leq$ edges.length $\leq 1000$

• $0 \leq x_i, y_i \leq$ n $- 1$

• $1 \leq {time}_i \leq 1000$

• $1 \leq$ passingFees[j] $\leq 1000$

• The graph may contain multiple edges between two nodes.

• The graph does not contain self loops.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.