You are given an undirected graph with $n$ nodes labeled from $0$ to $n - 1$, and an array edges where edges[i] = [u_i, v_i, cnt_i] indicates that there is an edge between nodes u_i and v_i subdivided into cnt_i new nodes.

Subdividing an edge means replacing the edge between u_i and v_i with a chain of cnt_i new intermediate nodes, resulting in cnt_i + 1 new edges.

Starting at node $0$, you can move to any adjacent node by traveling along an edge. Each step from one node to an adjacent node counts as $1$ move.

Return the total number of nodes (both original nodes and newly subdivided nodes) that can be reached from node $0$ in at most maxMoves moves.

Constraints:

• $0 \leq$ edges.length $\leq \min(n \cdot (n - 1) / 2, 10^4)$

• edges[i].length $= 3$

• $0 \leq u_i < v_i < n$

• There are no multiple edges in the graph.

• $0 \leq cnt_i \leq 10^4$

• $0 \leq$ maxMoves $\leq 10^9$

• $1 \leq n \leq 3000$

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.