You are given an integer n representing the number of cities labeled from $0$ to n $- 1$, and a $2 {D}$ integer array highways, where highways[i] = $[`city1_i`, `city2_i`, `toll_i`]$ indicates a bidirectional highway connecting city1_i and city2_i with a toll cost of toll_i. You are also given an integer discounts, which denotes the maximum number of discount coupons you can use.

Applying a discount to a highway halves its toll, rounded down to the nearest integer (that is, $\lfloor {toll} / 2 \rfloor$). You can use at most one discount coupon on any single highway traversal, and you may use at most discounts coupons during the entire journey.

Return the minimum total cost to travel from city $0$ to city n $- 1$. If city n $- 1$ cannot be reached from city $0$, return $-1$.

Constraints:

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

• $1 \leq$ highways.length $\leq 1000$

• highways[i].length $= 3$

• $0 \leq$ city1_i, city2_i $\leq$ n $- 1$

• city1_i $\neq$ city2_i

• $0 \leq$ toll_i $\leq 10^5$

• $0 \leq$ discounts $\leq 500$

• There are no duplicate highways.

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.