Shortest Path Between Cities with Tolls

Problem

You are given a road network as a weighted directed graph where edge weights represent toll costs. Find the minimum cost path between a source city and a destination city.

Input / Output

• Input: the number of cities, a list of directed weighted roads [u, v, toll], a source and a destination.
• Output: the minimum total toll from source to destination (and optionally the path).

Constraints

• 1 ≤ cities ≤ 10^4
• Non-negative edge weights

Example

cities = 5
roads = [[0,1,4],[0,2,2],[1,3,3],[2,1,1],[2,3,5],[3,4,2]]
source = 0, destination = 4
Output: 8  -- path: 0->2->1->3->4