You are given an integer n representing the number of nodes in an undirected graph, labeled from $0$ to $n - 1$. You are also given a $2$D integer array edges, where edges[i] $= [u_i, v_i, w_i]$ indicates an undirected edge between node $u_i$ and node $v_i$ with a repair cost of $w_i$. Additionally, you are given an integer k.

To traverse an edge, it must be repaired. If you have an amount of money equal to $C$, you can repair and use any edge with a repair cost of at most $C$.

Return the minimum amount of money required to travel from node $0$ to node $n - 1$ along a path containing at most k edges. If it is impossible to reach node $n - 1$ from node $0$ using at most k edges, return $-1$.

Constraints:

• $2 \le$ n $\le 5 imes 10^4$

• $1 \le$ edges.length $= m \le 10^5$

• edges[i] $= [u_i, v_i, w_i]$

• $0 \le u_i, v_i <$ n

• $1 \le w_i \le 10^9$

• $1 \le$ k $\le$ n

• There are no self loops or duplicate edges in the graph.

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.