Redundant Network Design

The first line of input contains two space-separated integers, 'V' and 'E', the number of vertices and edges.
The next 'E' lines each contain three space-separated integers, u, v, and w, representing an undirected edge between u and v with weight w.

Print a single integer representing the cost of the second-best MST.
If no second-best MST exists (e.g., the graph is already a tree), print -1.

The algorithm to solve this is:
1)Find the first MST and its total cost using an algorithm like Kruskal's. Keep a list of the edges that are part of this MST.
2)Iterate through every edge (u, v) with weight w_new that was not included in the first MST.
3)For each such edge, temporarily adding it to the MST creates a unique cycle. To form a new spanning tree, we must remove another edge from this cycle.
4)To find the smallest increase in cost, we must remove the heaviest edge on the path between u and v within the first MST.
5)Calculate the new tree's cost: MST_cost + w_new - w_heaviest.
6)The second-best MST cost is the minimum of these calculated costs that is strictly greater than the original MST cost.

Sample Input 1:

7 12
0 1 18
0 6 2
0 5 8
0 4 10
1 6 12
1 2 4
2 6 14
2 3 26
3 4 16
3 6 30
4 5 5
4 6 3

Sample Output 1:

44

Explanation for Sample 1:

1.  First, we find the MST. Its edges are `(0,6,2), (4,6,3), (1,2,4), (4,5,5), (1,6,12), (3,4,16)`. The total cost of this MST is 42.
2.  Now we consider an edge not in the MST, for example, `(2,6)` with weight 14. Adding it creates a cycle `2-1-6-2`. The path in the MST between 2 and 6 is `2-1-6`. The edges on this path are `(2,1,4)` and `(1,6,12)`.
3.  The heaviest edge on this path is `(1,6)` with weight 12.
4.  We swap: remove the edge of weight 12 and add the edge of weight 14.
5.  The new cost is `42 - 12 + 14 = 44`.
6.  After checking all other non-MST edges, this is found to be the smallest possible increase, so the second-best MST cost is 44.

Sample Input 2:

4 3
0 1 10
1 2 20
2 3 30

Sample Output 2:

-1

Explanation for Sample 2:

The graph is a line with 4 vertices and 3 edges. It is already a tree. There are no extra edges to swap in, so a second-best MST cannot be formed.

Expected Time Complexity:

The expected time complexity is O(E log V + E*V) for a simple implementation or O(E log V) with an advanced LCA-based approach. The simpler implementation is sufficient for the given constraints.

Constraints:

1 <= V <= 100
V-1 <= E <= V*(V-1)/2
0 <= u, v < V
1 <= w <= 1000
The graph is guaranteed to be connected.

Time limit: 1 sec