Elegant. Dijktra's Algorithm and Dynamic Programming
\nimport math\nfrom heapq import heapify, heappop as hpop, heappush as hpush\nclass Solution:\n    # O((|E| + |V|) * log(V)) Time and O(V + E) Space\n    def co
```\nimport math\nfrom heapq import heapify, heappop as hpop, heappush as hpush\nclass Solution:\n    # O((|E| + |V|) * log(V)) Time and O(V + E) Space\n    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n        mod = (10**9) + 7\n        graph = [set() for _ in range(n+1)]\n        distances = [math.inf] * (n + 1)\n        distances[n] = 0\n        \n        for source, dest, weight in edges:\n            graph[source].add((weight, dest))\n            graph[dest].add((weight, source))\n            \n\n        unexplored = [(0, n)]\n        heapify(unexplored)\n        explored = set()\n        \n        # dynamic-programming\n        # at every index of ways, where index represents the node-id\n        # we will store the number of ways we can reach this node\n        # from node-1, with condition node-1\'s distance from node-n\n        # is greater than this node\'s distance from node-n\n        ways = [0] * (n+1)\n        ways[n] = 1\n        \n        # dijkstra\'s algorithm\n        # we are calculating shortest distance of each node\n        # from node-n\n        # and, along with that we are calculating number of restricted paths\n        # from node-1 to node-n in bottom-up fashion\n        while len(unexplored) != 0:\n            weight, node = hpop(unexplored)\n            \n            if node in explored: continue\n            explored.add(node)\n            \n            for adj_weight, adj_node in graph[node]:\n                if adj_node in explored: continue\n                    \n                new_weight = adj_weight + weight\n                \n                # update shortest-distance\n                if new_weight < distances[adj_node]:\n                    distances[adj_node] = new_weight\n                    hpush(unexplored, (new_weight, adj_node))\n           \n                # update the number of ways/paths\n                # we know that we have already explored node\n                # so, we can use it\'s precomputed distance\n                if distances[adj_node] > distances[node]:\n                    ways[adj_node] += ways[node]\n                    \n        return ways[1] % mod\n                    \n\n```
['Dynamic Programming', 'Python3']