Emergency

All submissions for this problem are available.
There are N cities in the country and some of them are connected by bidirectional roads. To handle
any emergency situation, they need a emergency cell to be set up at some cities such that, in case of any
emergency in a city, the fire engine, the ambulance etc., can reach that city. Setting up a emergency
cell is expensive and as occurrence of a emergency situation is very rare, its just enough to have each city
connected ( possibly through other cities, by a path ) to a city which has an emergency cell.
Given the cost to setup emergency cell in each of the cities and the map of the country,
find the minimum amount of money government needs to spend. In other words, the Government needs to select
a set of cities S to set up emergency cells such that, every city in the country is connected to at least one
city in S.
Input
The first line contains the number of test cases T. T cases follow. Each test case starts with a line
containing N M, N is the number of cities numbered 1 to N and M is the number of bidirectional roads.
Next line contains N integers, the ith integer is the cost of setting up emergency cell in the ith city.
Each of the next M lines contains, x y , meaning x and y are directly connected by a bidirectional road.
There can be multiple roads between a pair of cities and some roads may even connect a city with itself.
Output
Output T lines, one for each case containing the required answer.
Constraints
1 <= T <= 5
1 <= N <= 100000
0 <= M <= 100000
0 <= cost_i <= 10000
0 <= x,y < N
Example
Input: 1 4 3 2 4 1 5 1 2 2 3 4 4 Output: 6
Explanation:
Minimum cost is 6, by selecting city 3 and city 4
Author:  flying_ant 
Tags  flying_ant 
Date Added:  1122011 
Time Limit:  0.403846 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, GO, NODEJS, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 