<p>There is a country of <code>n</code> cities numbered from <code>0</code> to <code>n - 1</code> where <strong>all the cities are connected</strong> by bi-directional roads. The roads are represented as a 2D integer array <code>edges</code> where <code>edges[i] = [x<sub>i</sub>, y<sub>i</sub>, time<sub>i</sub>]</code> denotes a road between cities <code>x<sub>i</sub></code> and <code>y<sub>i</sub></code> that takes <code>time<sub>i</sub></code> minutes to travel. There may be multiple roads of differing travel times connecting the same two cities, but no road connects a city to itself.</p>

<p>Each time you pass through a city, you must pay a passing fee. This is represented as a <strong>0-indexed</strong> integer array <code>passingFees</code> of length <code>n</code> where <code>passingFees[j]</code> is the amount of dollars you must pay when you pass through city <code>j</code>.</p>

<p>In the beginning, you are at city <code>0</code> and want to reach city <code>n - 1</code> in <code>maxTime</code><strong> minutes or less</strong>. The <strong>cost</strong> of your journey is the <strong>summation of passing fees</strong> for each city that you passed through at some moment of your journey (<strong>including</strong> the source and destination cities).</p>

<p>Given <code>maxTime</code>, <code>edges</code>, and <code>passingFees</code>, return <em>the <strong>minimum cost</strong> to complete your journey, or </em><code>-1</code><em> if you cannot complete it within </em><code>maxTime</code><em> minutes</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/06/04/leetgraph1-1.png" style="width: 371px; height: 171px;" /></p>

<pre>
<strong>Input:</strong> maxTime = 30, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
<strong>Output:</strong> 11
<strong>Explanation:</strong> The path to take is 0 -&gt; 1 -&gt; 2 -&gt; 5, which takes 30 minutes and has $11 worth of passing fees.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2021/06/04/copy-of-leetgraph1-1.png" style="width: 371px; height: 171px;" /></strong></p>

<pre>
<strong>Input:</strong> maxTime = 29, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
<strong>Output:</strong> 48
<strong>Explanation:</strong> The path to take is 0 -&gt; 3 -&gt; 4 -&gt; 5, which takes 26 minutes and has $48 worth of passing fees.
You cannot take path 0 -&gt; 1 -&gt; 2 -&gt; 5 since it would take too long.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> maxTime = 25, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
<strong>Output:</strong> -1
<strong>Explanation:</strong> There is no way to reach city 5 from city 0 within 25 minutes.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= maxTime &lt;= 1000</code></li>
	<li><code>n == passingFees.length</code></li>
	<li><code>2 &lt;= n &lt;= 1000</code></li>
	<li><code>n - 1 &lt;= edges.length &lt;= 1000</code></li>
	<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= n - 1</code></li>
	<li><code>1 &lt;= time<sub>i</sub> &lt;= 1000</code></li>
	<li><code>1 &lt;= passingFees[j] &lt;= 1000</code>&nbsp;</li>
	<li>The graph may contain multiple edges between two nodes.</li>
	<li>The graph does not contain self loops.</li>
</ul>

class Solution:
    def minCost(self, maxTime: int, edges: List[List[int]], passingFees: List[int]) -> int:
        # n cities 0..n-1
        # given an undirected edge list with times/weights(?)
        #   parallel edges are possible, but no self-loops

        # when you pass through a city u, you must pay passingFees[u]

        # starting at city 0, we want to get to city n-1 in at most maxTime
        # return the minimum cost of any path with that time constraint

        # want the minimum-cost path subject to a max time constraint

        # is there any path with total time <= maxTime?
        #
        # we can use Dijkstra to find the minimum time path from 0 to n-1
        #     if it exists then great, otherwise return -1

        # then suppose we're doing that Dijkstra algo
        #   we want to keep exploring longer time paths if they decrease cost
        #
        # so we want to revisit u at a later time t with cost c
        #   iff c is lower than earlier alternatives,
        #     so if c < minCost_{t' < t}(c'), conditional minimum cost -> Fenwick??

        # O(log(maxTime)) for this to work, versus O(maxTime), neat

        # a Fenwick tree per node, O(maxTime*n) memory
        n = len(passingFees)
        costTrees = [[math.inf]*(maxTime+2) for _ in range(n)]
        
        def minCost(u: int, t: int) -> float:
            """Returns the minimum cost over paths reaching u in time <= t"""
            t += 1 # since we want the min cost for time 0 as well
            ans = math.inf
            while t:
                ans = min(ans, costTrees[u][t])
                t &= t-1
            return ans

        def reduceCost(u: int, t: int, c: int) -> None:
            tree = costTrees[u]
            t += 1
            while t < maxTime+2:
                tree[t] = min(tree[t], c)
                t += t & -t

        # adjacency list, handle parallel edges by recording only the minimum-weight one
        adj = [defaultdict(lambda: math.inf) for _ in range(n)]
        for u, v, t in edges:
            if t > maxTime: continue

            adj[u][v] = min(adj[u][v], t)
            adj[v][u] = min(adj[v][u], t)

        pq = [(0, passingFees[0], 0)] # time, cost, u
        reduceCost(u=0, t=0, c=passingFees[0])
        while pq:
            t, c, u = heappop(pq)

            if c > minCost(u, t):
                continue # stale entry

            for v, dt in adj[u].items():
                tv = t+dt
                cv = c + passingFees[v]

                if tv > maxTime:
                    continue
                if cv >= minCost(v, tv): 
                    continue # already enqueued a cheaper path at least as fast

                # record that we have a new cheapest path to v, costing cv, so we don't later
                # push any paths with t' >= t and c' >= cv
                reduceCost(v, tv, cv)
                heappush(pq, (tv, cv, v))

        # explored all paths from 0 to all other nodes, in time order, ensuring cost
        # drops monotonically with time to its minimum value
        
        min_cost = min(costTrees[n-1])
        return min_cost if min_cost < math.inf else -1
893