Python3  Djikstra+Backtracking (For somewhat tighter constraints)
Use Djikstra to find the shortest distance to come back to 0 for every node. This shortest distance will be used as a pruning/terminating condition while backtr
Use Djikstra to find the shortest distance to come back to 0 for every node. This shortest distance will be used as a pruning/terminating condition while backtracking.\n\n\nTC: 4^maxTime (though will be reduced due to pruning and for this question it will always be less than 4^10 as maxTime is 100 at maximum and every edge is 10 at minimum)\n\n# Code\n```python3 []\nclass Solution:\n    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:\n        \n        graph = defaultdict(list)\n        for x,y,time in edges:\n            graph[x].append((y, time))\n            graph[y].append((x, time))\n\n        n = len(values)\n        best_dist = [inf]*n\n        best_dist[0] = 0\n        heap = [(0,0)]\n        while heap:\n            val, node = heapq.heappop(heap)\n            if val>best_dist[node]:\n                continue\n            for ne, t in graph[node]:\n                nval = t+val\n                if best_dist[ne]<=nval:\n                    continue\n                best_dist[ne]=nval\n                heapq.heappush(heap, (nval, ne))\n    \n        visited = set()\n        def backtrack(node, rem):\n            \n            res = 0\n            for ne, time in graph[node]:\n                if best_dist[ne]+time>rem:\n                    continue\n                if ne in visited:\n                    res = max(res, backtrack(ne, rem-time))\n                else:\n                    visited.add(ne)\n                    res = max(res, values[ne]+backtrack(ne, rem-time))\n                    visited.remove(ne)\n            return res\n        visited.add(0)\n        return values[0]+backtrack(0, maxTime)\n\n\n\n\n            \n```
['Python3']