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

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        graph = collections.defaultdict(list)
        for u, v, time in roads:
            graph[u].append([v, time])
            graph[v].append([u, time])

        start = 0
        target = n - 1

        # set minimum distance of all nodes except start to infinity.
        # min_dist[i] = [minimum time from start, number of ways to get to node i in min time]
        min_dist = {i:[float('inf'), 0] for i in graph.keys()}
        min_dist[start] = [0, 1] # [min time from start to start = 0, number of ways = 1]

        # dijkstra
        # Heap nodes in the format (elapsed time to get to that node, node index)
        heap = [(0, start)]
        while heap:
            elapsed_time, node = heapq.heappop(heap) 
            
            # if nodes getting popped have a higher elapsed time than minimum time required
            # to reach end node, means we have exhausted all possibilities
            # Note: we can do this only because time elapsed cannot be negetive
            # if elapsed_time > min_dist[target][0]:
            #     break

            for neighbor_node, neighbor_time in graph[node]:
                if (elapsed_time + neighbor_time) > min_dist[neighbor_node][0]:
                    continue

                elif (elapsed_time + neighbor_time) == min_dist[neighbor_node][0]:
                    min_dist[neighbor_node][1] += min_dist[node][1]

                else:
                    min_dist[neighbor_node][0] = elapsed_time + neighbor_time
                    min_dist[neighbor_node][1] = min_dist[node][1]
                    heapq.heappush(heap, (elapsed_time + neighbor_time, neighbor_node))

        return min_dist[target][1] %(pow(10,9)+7)



        # def dijkstra(src):
        #     dist = [float('inf')] * n
        #     ways = [0] * n
        #     minHeap = []
        #     heapq.heappush(minHeap, (0, src))
        #     dist[src] = 0
        #     ways[src] = 1
        #     while minHeap:
        #         d, u = heapq.heappop(minHeap)

        #         for v, time in graph[u]:
        #             if dist[v]
283