Straightforward Python Dijkstra's
\n\n# Code\n\nfrom heapq import heapify, heappush, heappop\nclass Solution:\n    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n\n        adj = c
\n\n# Code\n```\nfrom heapq import heapify, heappush, heappop\nclass Solution:\n    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n\n        adj = collections.defaultdict(list)\n\n        for r in roads:\n            adj[r[0]].append((r[1], r[2]))\n            adj[r[1]].append((r[0], r[2]))\n        \n        heap = []\n\n        heapify(heap)\n        heappush(heap, (0, 0))\n\n        dist = [float(\'inf\')] * n\n        dist [0] = 0\n        ways = [0] * n\n        ways[0] = 1 # ways to visit 0 is 1 by default\n        MOD = 10**9 + 7\n\n        while heap:\n            di, node = heappop(heap)\n\n            for nn in adj[node]:\n                adj_node = nn[0]\n                adj_dist = nn[1]\n\n                if di + adj_dist < dist[adj_node]:\n                    ways[adj_node] = ways[node]\n                    dist[adj_node] = di + adj_dist\n                    heappush(heap, (di + adj_dist, adj_node))\n                elif di + adj_dist == dist[adj_node]:\n                    ways[adj_node] = (ways[adj_node] + ways[node])%MOD\n    \n        return ways[n-1] % MOD\n\n\n\n            \n\n        \n```
['Python3']