Python 3 | Dijkstra, DFS, DAG pruning | Explanation
Implementation\n- The solution is basically an implementation based on hint, please seee below comments for detail\n### Explanation\n\nclass Solution:\n    def 
### Implementation\n- The solution is basically an implementation based on `hint`, please seee below comments for detail\n### Explanation\n```\nclass Solution:\n    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n        graph = collections.defaultdict(list)       # build graph\n        for a, b, w in edges:\n            graph[a].append((w, b))\n            graph[b].append((w, a))\n        heap = graph[n]\n        heapq.heapify(heap)\n        d = {n: 0}\n        while heap:                                 # Dijkstra from node `n` to other nodes, record shortest distance to each node\n            cur_w, cur = heapq.heappop(heap)\n            if cur in d: continue\n            d[cur] = cur_w\n            for w, nei in graph[cur]:\n                heapq.heappush(heap, (w+cur_w, nei))\n        graph = collections.defaultdict(list)\n        for a, b, w in edges:                       # pruning based on `restricted` condition, make undirected graph to directed-acyclic graph\n            if d[a] > d[b]:\n                graph[a].append(b)\n            elif d[a] < d[b]:\n                graph[b].append(a)\n        ans, mod = 0, int(1e9+7)\n        @cache\n        def dfs(node):                              # use DFS to find total number of paths\n            if node == n:\n                return 1\n            cur = 0 \n            for nei in graph[node]:\n                cur = (cur + dfs(nei)) % mod\n            return cur    \n        return dfs(1)\n```
['Depth-First Search', 'Python', 'Python3']