You are given an integer n representing the number of nodes in a connected undirected graph, with nodes 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] denotes an undirected edge connecting node u_i and node v_i with weight w_i.

The cost of a path between node $0$ and node n $- 1$ is defined as the sum of all edge weights along that path, excluding the weight of exactly one edge with the maximum weight on that path.

Return the minimum possible cost of a path from node $0$ to node n $- 1$.

Constraints:

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

• n $- 1 \leq$ edges.length $\leq 10^9$

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

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

• [u_i, v_i] != [u_j, v_j] for all $i \neq j$

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

• The 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.