You are given an integer n representing the number of vertices in an undirected connected graph, with vertices labeled from $0$ to n $- 1$. You are also given a two dimensional integer array edges, where edges[i] = [u_i, v_i, w_i] denotes an undirected edge between vertices u_i and v_i with weight w_i, and an integer k.

You can remove any number of edges from the graph to split it into at most k connected components. The cost of a connected component is defined as the maximum weight of any edge present in that component, or $0$ if the component contains no edges.

Return the minimum possible maximum cost among all components after splitting the graph into at most k connected components.

Constraints:

• $1 \leq$ n $\leq 5 \times 10^4$

• $0 \leq$ edges.length $\leq 10^5$

• edges[i].length $= 3$

• $0 \leq$ u_i, v_i $<$ n

• $1 \leq$ w_i $\leq 10^6$

• $1 \leq$ k $\leq$ n

• The input graph is 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.