<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 = len(passingFees)

        # adjacency list # TODO: only use shortest path between each pair
        adj = [[] for _ in range(n)]
        for u, v, dt in edges:
            if dt > maxTime: continue
            adj[u].append((v, dt))
            adj[v].append((u, dt))

        # modified Dijkstra
        #    > main idea: explore paths in order by cost
        #    > to visit a node later, we require
        times = [math.inf]*n
        costs = [math.inf]*n
        times[0] = 0
        costs[0] = passingFees[0]
        pq = [(costs[0], times[0], 0)] # explore by cost asc | time <= maxTime
        while pq:
            c, t, u = heappop(pq)

            if u == n-1:
                return c # first encounter of n-1 ord by cost: we found the min cost

            if c > costs[u] and t > times[u]: continue # stale entry in heap

            # this path to u is either the minimum cost, or the minimum time
            # for costs > u as we explore by costs > u
            for v, dt in adj[u]:
                vt = t+dt
                vc = c+passingFees[v]

                if vt > maxTime: continue # illegal path
                
                if vc < costs[v]:
                    # new lowest cost, want to explore all legal paths from here to get the min cost
                    costs[v] = vc
                    # times[v] = vt
                    heappush(pq, (vc, vt, v))
                elif vt < times[v]:
                    # higher cost than current min-cost path, but less time. worth exploring
                    times[v] = vt
                    heappush(pq, (vc, vt, v))
                # else: neither the best cost nor best time, ignore it

        return -1 # never encountered n-1 via a path of suitable distance

        # so why does it work? What about the edge case where we pushed
        #    > a low-cost, high-time path to u | we can't reach n-1 in time
        #    > a huge cost, low-time path to u, valid path but suboptimal cost
        #    > mid cost, mid-time path to u, the optimum one, but one that we'd encounter
        #        after the prior two?
        #
        #    > because a low-cost, high-time path means the passing cost of u is low cost
        #    > a high-cost, low-time path thus requires a high-cost intermediate node to high total cost
        #    > a mid-cost, mid-time path involves a different intermediate node(s) with lower total costs
        #
        # We explore in cost order so we'd see the mid-cost, mid-time route instead
        # and only later see the high-cost, low-time route intead
        # paths from the mid-cost mid-time route would encounter the destination first
        # and therefore we'd get the min cost path

        # I still think there's an edge case possible but can't prove it
        # 
        # After more cases of trying to do a counter-example:
        #   > high cost, low time involves visiting several different intermeidate nodes than
        #    > a low-cost, high time path
        # the cost is paid "up front" to visit a node, so the cost is part of the queue BEFORE
        #  we explore paths
        # whereas the time for the edge is only added after we start exploring
        #
        # for those expensive paths, they require more expensive nodes than the low-cost-high-time path
        # those nodes are explored from later, by definition
        # exploring in cost order means for any cost we've explored all nodes, and thus all times,
        # available at costs <= T
        # any times we find later at same cost have same cost, duh, and maybe earlier times
        # then we start popping the next highest cost, which unlocks new lowest times
        # so as cost increases, times monotonically decrease to all edges as we expect
        # we ONLY want to accept a cost increase if the time decreases
        # a later node of higher cost might be encountered with an even shorter time, but it will
        # be encountered later because we process in cost order

        # this is kind of mind-bending, but it makes sense now, mostly
235