python3 backtracking
\n\n# Code\n\nclass Solution:\n    def maximalPathQuality(self,values, edges, maxTime):\n        s = set([0])\n        d = defaultdict(list)\n        cost = def
\n\n# Code\n```\nclass Solution:\n    def maximalPathQuality(self,values, edges, maxTime):\n        s = set([0])\n        d = defaultdict(list)\n        cost = defaultdict(int)\n        ans = 0\n        for a,b,c in edges:\n            d[a].append(b)\n            d[b].append(a)\n            cost[(a,b)] = c\n            cost[(b,a)] = c\n\n        def bt(node,total,remTime):\n            nonlocal ans\n            if node == 0:\n                ans = max(ans,total)   \n            for e in d[node]:\n                if remTime-cost[(node,e)] >=0:\n                    if e not in s:\n                        s.add(e)\n                        bt(e,total+values[e],remTime-cost[(node,e)])\n                        s.remove(e)\n                    else:\n                        bt(e,total,remTime-cost[(node,e)])\n\n        bt(0,values[0],maxTime)\n        return ans \n```
['Python3']