<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
import collections

MOD = 10**9 + 7  # A large prime number for modulo operations

class Solution:
    def countPaths(self, n: int, roads: list[list[int]]) -> int:
        # Build the graph using an adjacency list
        graph = collections.defaultdict(list)
        for u, v, edgeWeight in roads:
            graph[u].append((v, edgeWeight))
            graph[v].append((u, edgeWeight))
        
        # Initialize the distances array with infinity and number of ways array with 0
        dist = [float('inf')] * n  # Stores shortest distances from node 0 to all other nodes
        ways = [0] * n  # Stores the number of ways to reach each node with the shortest distance
        
        # Starting from node 0
        dist[0] = 0  # Distance to start node is 0
        ways[0] = 1  # There is exactly 1 way to reach the start node (itself)

        print(graph)  # Print the graph for debugging purposes
        
        # Priority queue for Dijkstra's algorithm
        pq = [(0, 0)]  # (distance, node) pairs, starting with the source node 0
        
        while pq:
            current_dist, node = heapq.heappop(pq)  # Pop the node with the smallest distance
            
            # # If we have already found a shorter way to this node, skip processing
            # print("current_dist ", current_dist)
            # print("dist[node], ", dist[node])
            # if current_dist > dist[node]:
            #     continue
            
            # Explore neighbors of the current node
            for adjNode, edgeWeight in graph[node]:
                new_dist = current_dist + edgeWeight  # Calculate new possible distance
                
                # If a shorter path to the adjacent node is found
                if new_dist < dist[adjNode]:
                    dist[adjNode] = new_dist  # Update shortest distance to the adjacent node
                    ways[adjNode] = ways[node]  # Reset the number of ways to reach the adjacent node
                    heapq.heappush(pq, (new_dist, adjNode))  # Push the updated distance and node to the queue
                
                # If another path with the same shortest distance is found
                elif new_dist == dist[adjNode]:
                    ways[adjNode] = (ways[adjNode] + ways[node]) % MOD  # Add to the number of ways to reach the adjacent node
        
        # The number of ways to reach node n-1 in the shortest time
        return ways[n-1]

24700