Python3 - BFS Solution - Beats 98%
Code
# Code
```python3 []
class Solution:
    def maximalPathQuality(self, nodeValues: List[int], edges: List[List[int]], maxAllowedTime: int) -> int:
        # Build the adjacency list representation of the graph
        graph = defaultdict(list)
        for startNode, endNode, travelTime in edges:
            graph[startNode].append((endNode, travelTime))
            graph[endNode].append((startNode, travelTime))

        # Initialize the queue for BFS traversal
        # (currentNode, currentTime, pathValueSum, visitedNodes)
        bfsQueue = deque([(0, 0, nodeValues[0], [0])])

        # Stores (maxValueReached, minTimeReached) for each node
        nodeVisitInfo = [(-1, -1)] * len(nodeValues)
        nodeVisitInfo[0] = (nodeValues[0], 0)

        maxPathQuality = 0  # Stores the maximum path quality found

        while bfsQueue:
            currentNode, elapsedTime, currentPathValue, visitedNodes = bfsQueue.popleft()

            # If we return to node 0, update max path quality
            if currentNode == 0:
                maxPathQuality = max(maxPathQuality, currentPathValue)

            # Explore neighbors of the current node
            for neighborNode, travelTime in graph[currentNode]:
                if elapsedTime + travelTime > maxAllowedTime:
                    continue  # Skip if time exceeds the allowed limit

                newPathValue = currentPathValue
                if neighborNode not in visitedNodes:
                    newPathValue += nodeValues[neighborNode]  # Add value only if first visit

                # Optimization: Skip paths that are worse than already found ones
                if elapsedTime + travelTime >= nodeVisitInfo[neighborNode][1] and newPathValue < nodeVisitInfo[neighborNode][0]:
                    continue

                # Append the new path to the queue
                bfsQueue.append((neighborNode, elapsedTime + travelTime, newPathValue, visitedNodes + [neighborNode]))

                # Update node visit information with the best value and earliest time
                nodeVisitInfo[neighborNode] = (newPathValue, elapsedTime + travelTime)

        return maxPathQuality
```
['Array', 'Breadth-First Search', 'Graph', 'Python3']