Number of Ways to Arrive at Destination LeetCode solution in Python

1
class Solution:
2
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
3
        graph = defaultdict(dict)
4
        for u, v, w in roads:
5
            graph[u][v] = graph[v][u] = w
6
        dist = {i: float(inf) for i in range(n)}
7
        ways = {i: 0 for i in range(n)}
8
        dist[0], ways[0] = 0, 1
9
        heap = [(0, 0)]
10
        while heap:
11
            d, u = heapq.heappop(heap)
12
            if dist[u] < d:
13
                continue
14
            for v in graph[u]:
15
                if dist[v] == dist[u] + graph[u][v]:
16
                    ways[v] += ways[u]
17
                elif dist[v] > dist[u] + graph[u][v]:
18
                    dist[v] = dist[u] + graph[u][v]
19
                    ways[v] = ways[u]
20
                    heapq.heappush(heap, (dist[v], v))
21
        return ways[n - 1] % ((10**9) + 7)