Dijkstra's shortest paths for each node, then DFS + Memo, O(V + E * log V)
find each node shortest distance to node n;\n2. dfs from n to 1, + memoization, to get total number of paths;\n\nSortedList, O(log n) remove.\n\ntime: O(V + E *
1. find each node shortest distance to node n;\n2. dfs from n to 1, + memoization, to get total number of paths;\n\nSortedList, O(log n) remove.\n\ntime: O(V + E * log V).\nhttps://en.wikipedia.org/wiki/Dijkstra%27s_algorithm\n\n```\nfrom sortedcontainers import SortedList, SortedDict, SortedSet\nclass Solution:\n    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n        # 1. find each node dist to n\n        # 2. dfs from n to 1, + memoization.\n        g = defaultdict(list)\n        for u, v, w in edges:\n            g[u].append((w, v))\n            g[v].append((w, u))\n        d = defaultdict(int)\n        for i in range(1, n+1):\n            d[i] = float("inf")\n        d[n] = 0\n                \n        h = SortedList([(0,n)])\n        while h:\n            dist, u = h.pop(0)\n            # print(u, "dist:", dist)\n            for w, v in g[u]:\n                if dist + w < d[v]:\n                    h.discard((d[v], v))\n                    d[v] = dist + w\n                    h.add((d[v], v))\n        # print(d)\n        f = {}\n        ans = self.dfs(g, d, n, f)\n                \n        return ans\n    \n    def dfs(self, g, d, u, f):\n        if u == 1:\n            return 1\n        ans = 0\n        MOD = 10**9 + 7\n        if u in f:\n            return f[u]\n        for _, v in g[u]:\n            if d[v] > d[u]:\n                ans += self.dfs(g, d, v, f)\n        \n        f[u] = ans % MOD\n        return f[u]\n```
['Python']