Copiado al portapapeles
Descripción
Kaido el rey de las bestias junto con toda su tripulación pirata tomaron el control del país de Wano hace 20 años, ahora le toca a Luffy y a sus amigos salvar al país juntos con sus habitantes. Para eso tienen que hacer un sinfín de misiones para lograr su objetivo.
Ahora ellos intentan realizar una de las misiones. La misión es llegar a la capital del país y difundir un rumor acerca de formar un ejército rebelde para luchar contra Kaido y toda su tripulación pirata.
Luffy sabe que hay $n$ habitantes en la capital. Algunos habitantes son amigos entre sí y comparten la información que obtuvieron. Por los 20 años en los que Kaido gobernó el país de Wano por ende los habitantes del país le tienen miedo asi que Luffy sabe que puede sobornar a cada habitante para que comience a difundir el rumor; El $i$-ésimo habitante quiere $c_{i}$ monedas de oro a cambio de difundir el rumor. Cuando un habitante escucha el rumor, se lo cuenta a todos sus amigos, y ellos comienzan a difundir el rumor a sus amigos (gratis), y así sucesivamente.
La búsqueda finaliza cuando todos los $n$ habitantes conocen el rumor. ¿Cuál es la cantidad mínima de monedas de oro que Luffy necesita gastar para terminar la misión?
Entrada
La primera línea contiene dos números enteros $n$ y $m$ $(1 \leq n \leq 10^{5}, 0 \leq m \leq 10^{5})$ — el número de habitantes en la capital del país y el número de pares de amigos que existen.
La segunda línea contiene $n$ números enteros $c_{i}$ $(0 \leq c_{i} \leq 10^{9})$, la cantidad de monedas de oro que el $i$-ésimo habitante del país pide para comenzar a difundir el rumor.
Luego siguen $m$ líneas, cada una de las cuales contiene un par de números $(x_{i}, y_{i})$ que representan que los habitantes $x_{i}$ y $y_{i}$ son amigos $(1 \leq x_{i}, y_{i} \leq n, x_{i} ≠ y_{i})$. Se garantiza que cada par aparece como máximo una vez.
Salida
Imprime un número: la cantidad mínima de monedas de oro que Luffy tiene que gastar para terminar la misión.
Ejemplo Entrada
5 2 2 5 3 4 8 1 4 4 5
Ejemplo Salida
10
Ayuda
Ejemplo entrada 2
10 0
1 2 3 4 5 6 7 8 9 10
Ejemplo salida 2
55
Ejemplo entrada 3
10 5
1 6 2 7 3 8 4 9 5 10
1 2
3 4
5 6
7 8
9 10
Ejemplo salida 3
15
En el primer ejemplo, la mejor decisión es sobornar al primer habitante (difundirá el rumor al cuarto habitante y el cuarto lo difundirá al quinto). También Luffy tiene que sobornar al segundo y al tercer personaje, para que conozcan el rumor.
En el segundo ejemplo, Luffy tiene que sobornar a todos.
En el tercer ejemplo la decisión óptima es sobornar al primero, al tercero, al quinto, al séptimo y al noveno.