Untitled

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        graph = defaultdict(dict)
        for u, v, t in roads:
            graph[u][v] = t
            graph[v][u] = t
        
        distance = [math.inf] * n
        ways = [1] * n
        processed = [False] * n
        distance[0] = 0
        queue = [(0,0)]
        heapq.heapify(queue)
        while queue:
            _, u = heapq.heappop(queue)
            if processed[u]:
                continue
            processed[u] = True
            for v, vt in graph[u].items():
                if processed[v]:
                    continue
                if distance[v] == distance[u] + vt:
                    ways[v] += 1
                else:
                    distance[v] = min(distance[v], distance[u] + vt)
                heapq.heappush(queue, (distance[v], v))
        return ways[n - 1] % (10**9 + 7)