<p>You are in a city that consists of <code>n</code> intersections numbered from <code>0</code> to <code>n - 1</code> with <strong>bi-directional</strong> roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections.</p>

<p>You are given an integer <code>n</code> and a 2D integer array <code>roads</code> where <code>roads[i] = [u<sub>i</sub>, v<sub>i</sub>, time<sub>i</sub>]</code> means that there is a road between intersections <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code> that takes <code>time<sub>i</sub></code> minutes to travel. You want to know in how many ways you can travel from intersection <code>0</code> to intersection <code>n - 1</code> in the <strong>shortest amount of time</strong>.</p>

<p>Return <em>the <strong>number of ways</strong> you can arrive at your destination in the <strong>shortest amount of time</strong></em>. Since the answer may be large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/17/graph2.png" style="width: 235px; height: 381px;" />
<pre>
<strong>Input:</strong> n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes.
The four ways to get there in 7 minutes are:
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6
</pre>

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

<pre>
<strong>Input:</strong> n = 2, roads = [[1,0,10]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes.
</pre>

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

<ul>
	<li><code>1 &lt;= n &lt;= 200</code></li>
	<li><code>n - 1 &lt;= roads.length &lt;= n * (n - 1) / 2</code></li>
	<li><code>roads[i].length == 3</code></li>
	<li><code>0 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt;= n - 1</code></li>
	<li><code>1 &lt;= time<sub>i</sub> &lt;= 10<sup>9</sup></code></li>
	<li><code>u<sub>i </sub>!= v<sub>i</sub></code></li>
	<li>There is at most one road connecting any two intersections.</li>
	<li>You can reach any intersection from any other intersection.</li>
</ul>

import heapq
from collections import defaultdict

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        MOD = 10**9 + 7
        
        # Adjacency list
        adj = defaultdict(list)
        for info in roads:
            start, end, time = info[0], info[1], info[2]
            adj[start].append((end, time))
            adj[end].append((start, time))
        
        # Time to reach each node, initialized to infinity
        time_arr = [float("inf")] * n
        time_arr[0] = 0  # Starting at node 0
        
        # Number of ways to reach each node
        path_count = [0] * n
        path_count[0] = 1  # Only 1 way to start at node 0
        
        # Min-heap priority queue (time, node)
        pq = []
        heapq.heapify(pq)
        heapq.heappush(pq, (0, 0))  # Start with (time 0, node 0)

        while pq:
            time, node = heapq.heappop(pq)

            # If this time is already worse than the best time recorded, skip it
            if time > time_arr[node]:
                continue
            
            # Traverse neighbors
            for nd, tm in adj[node]:
                new_time = time + tm

                # If found a shorter path to 'nd'
                if new_time < time_arr[nd]:
                    time_arr[nd] = new_time  # Update shortest time
                    path_count[nd] = path_count[node]  # Inherit path count from the current node
                    heapq.heappush(pq, (new_time, nd))  # Push to heap
                
                # If found another path with the same shortest time
                elif new_time == time_arr[nd]:
                    path_count[nd] = (path_count[nd] + path_count[node]) % MOD  # Add number of ways
                    
        return path_count[n-1]  # Number of ways to reach node n-1

244