You're planning a road trip from one city to another. There are n cities connected by one-way roads, and each road has a toll cost.

In this problem, taking one road counts as using one toll road.

You're given an array roads where roads[i] = [from_i, to_i, price_i] , indicating the toll cost to travel from city to city to_i.

All roads are one-way, meaning each road only allows travel in the specified direction to city to_i.

You're also given:

src, dst: your trip's starting and destination cities.

An integer maxTolls, the maximum number of toll roads you're willing to take on your trip.

Return the minimum total travel cost to go from src to dst using at most maxTolls toll roads. If it's not possible under these constraints, return -1.

Example 1:

Input: n = 4, roads = [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 3, 500]]
, src = 0, dst = 3, maxTolls = 3
Output: 300
Explanation: Route 0 → 1 → 2 → 3 pays 3 toll roads, total toll cost = 100 + 100 + 100 = 300 (cheaper than direct 0 → 3 with a toll cost of 500 (1 toll road)).

Example 2:

Input: n = 3, roads = [[0, 1, 150], [1, 0, 100], [1, 2, 100]]
src = 0, dst = 2, maxTolls = 5
Output: 250
Explanation: The cheapest path is 0 → 1 → 2 with total cost 250. It uses exactly 2 toll roads, which is within the limit.

Example 3:

Input: n = 4, roads = [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 3, 500]], 
src = 0, dst = 3, maxTolls = 1
Output: 500
Explanation: Only one toll road is allowed. The direct path 0 → 3 costs 500 and fits the limit. The cheaper path 0 → 1 → 2 → 3 uses three toll roads, which exceeds the maxTolls limit.

Example 4:

Input:n = 3, roads = [[0, 1, 200], [1, 2, 200]]
src = 0, dst = 2, maxTolls = 0
Output: -1
To reach city 2, you must take two toll roads: 0 → 1 and 1 → 2. Since maxTolls = 0, no road can be used, so the trip is not possible.

Constraints

1 <= n <= 100

0 <= roads.length <= (n×(n-1))

roads[i].length == 3

0 <= from_i, to_i < n

from_i != to_i

1 <= price_i <= 104

There will not be any multiple roads between two cities.

0 <= src, dst, maxTolls < n

0 <= src, dst < n, 0 <= maxTolls <= n - 1

89. Cheapest Trip within K Toll Roads (Bellham Ford)