Python - Dijstra and DP DFS (No @lru_cache)
python\nfrom heapq import heappush, heappop\n\nclass Solution:\n    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n        graph = { i:
```python\nfrom heapq import heappush, heappop\n\nclass Solution:\n    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n        graph = { i: [] for i in range(1, n + 1) }\n        \n        for u, v, w in edges:\n            graph[u].append((v, w))\n            graph[v].append((u, w))\n            \n        toLast = self.dijkstra(n, graph)\n        \n        return self.dfs(1, graph, toLast, {}) % (10 ** 9 + 7)\n                   \n    def dijkstra(self, n: int, graph: dict) -> dict:\n        shortest = { n: float(\'inf\') for n in range(1, n + 1) }\n        shortest[n] = 0\n        \n        queue = [ (0, n) ]\n        \n        while queue:\n            d, u = heappop(queue)\n            \n            for v, w in graph[u]:\n                if shortest[v] > d + w:\n                    shortest[v] = d + w\n                    heappush(queue, (d + w, v))\n                            \n        return shortest\n    \n    def dfs(self, u: int, graph: dict, toLast: dict, seen: dict) -> int:\n        if u == len(graph):\n            return 1\n        \n        if u in seen:\n            return seen[u]\n        \n        res = 0\n        for v, _ in graph[u]:\n            if toLast[u] > toLast[v]:\n                res += self.dfs(v, graph, toLast, seen)\n        \n        seen[u] = res\n        return seen[u]\n```
[]