Python - Dijkstra's Algorithm
\nclass Solution:\n    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n        graph = defaultdict(dict)\n        for u, v, w in roads:\n         
```\nclass Solution:\n    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n        graph = defaultdict(dict)\n        for u, v, w in roads:\n            graph[u][v] = graph[v][u] = w\n        dist = {i:float(inf) for i in range(n)}\n        ways = {i:0 for i in range(n)}\n        dist[0], ways[0] = 0, 1\n        heap = [(0, 0)]\n        while heap:\n            d, u = heapq.heappop(heap)\n            if dist[u] < d: \n                continue\n            for v in graph[u]:\n                if dist[v] == dist[u] + graph[u][v]:\n                    ways[v] += ways[u]\n                elif dist[v] > dist[u] + graph[u][v]:\n                    dist[v] = dist[u] + graph[u][v]\n                    ways[v] = ways[u]\n                    heapq.heappush(heap, (dist[v], v))\n        return ways[n-1] % ((10 ** 9) + 7)\n```
['Python']