There is an undirected graph with $n$ nodes labeled from $0$ to $n - 1$, where node $i$ has a value given by values[i]. You are provided a $2$D integer array edges, where edges[j] = [u_j, v_j, time_j] denotes an undirected edge between node $u_j$ and node $v_j$ that takes $time_j$ time units to traverse. You are also given an integer maxTime.

A valid path is any sequence of nodes that begins at node $0$, ends at node $0$, and has a total traversal time of at most maxTime. Nodes and edges may be visited multiple times. The quality of a path is defined as the sum of values[i] across all unique nodes visited along the path, meaning the value of each visited node is counted only once.

Return the maximum path quality among all valid paths.

Constraints:

• n == values.length

• $1 \leq n \leq 1000$

• $0 \leq$ values[i] $\leq 10^8$

• $0 \leq$ edges.length $\leq 2000$

• edges[j].length $== 3$

• $0 \leq u_j < v_j \leq n - 1$

• $10 \leq time_j \leq 100$

• $10 \leq$ maxTime $\leq 100$

• All the pairs $[u_j, v_j]$ are unique.

• There are at most $4$ edges connected to each node.

• The graph may not be connected.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.