I was here
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n\n        if n==1:\n            return 1\n        \n        adjl = {}\n        for road in roads:\n            if road[0] not in adjl:\n                adjl[road[0]] = { road[1] : road[2] }\n            else:\n                adjl[road[0]][road[1]] = road[2]\n            if road[1] not in adjl:\n                adjl[road[1]] = { road[0] : road[2] }\n            else:\n                adjl[road[1]][road[0]] = road[2]\n        shortest  = {}\n        minHeap = []\n        heapq.heappush(minHeap,(0,0))\n        while minHeap and len(shortest)!=n:\n            k=heapq.heappop(minHeap)\n            if k[1] in shortest:\n                continue\n            shortest[k[1]]= k[0] \n            for neighbour,weight in adjl[k[1]].items():\n                if neighbour not in shortest:\n                    heapq.heappush(minHeap,(weight + k[0],neighbour))\n        \n        heap = []\n        for a,b in shortest.items():\n            heapq.heappush(heap,(b*-1,a))\n        \n        no_of_paths = [0]*n\n        no_of_paths[n-1] = 1\n        while heap:\n            p = heapq.heappop(heap)\n            for k,_ in adjl[p[1]].items():\n                if ((p[0]*-1)-adjl[p[1]][k])==shortest[k]:\n                    no_of_paths[k] += no_of_paths[p[1]]\n        return no_of_paths[0]%(10**9+7)\n    \n                \n            \n```
['Dynamic Programming', 'Graph', 'Topological Sort', 'Shortest Path', 'Python3']