Nova Poshta#7378
"Nova Poshta" is a rapid delivery service for goods and cargo. The service operates through warehouses, which are interconnected by existing and licensed routes. Each route connects exactly two warehouses.
To ensure seamless operations, additional routes may need to be established so that any two warehouses can be connected directly or indirectly through other warehouses. The cost of obtaining a license at each of the warehouses is specified in the array . To open a new route between warehouses and , licenses must be acquired at both warehouses, incurring a total cost of C_i + C_j.
Determine the minimum total cost required to enable full operational connectivity for the "Nova Poshta" delivery service.
The first line contains the integers and , where 0 \leq N \leq 1000. The second line lists elements of the array , with 0 \leq C_i \leq 1000000. The following lines each contain a pair of numbers representing the already established routes. All numbers are natural numbers.
Output the minimum cost necessary to ensure full operational connectivity for the delivery service.
Example 1