Petya lives in a city named Mayapur. As in the morning, everybody likes to drink hot tea in the bed. So the citizens of Mayapur needs milk to produce tea. For this purpose, they want to be able to go to a milkmen using the bi-directional roads. There are m roads in the city. Every year these roads become unfit for transportation, hence they have to be repaired each year.

Last Year Petya repaired those roads. as Petya is short in money last year he repaired them such that with minimum budget everyone get milk from someone. Since then he received some complaints that some people have to walk for a long distance to get milk so this year Petya want to repair the roads such that everyone can go to their nearest milkmen to get milk. So he has to select some roads to repair such that every citizen is connected to at least one milkman and that milkman is the nearest one for that citizen. For repairing each road he needs to pay the necessary cost. As he does not want to spend a lot of money in it, He wants to minimize the cost needed in this project. Note that a milkmen does not need to go to some other milkmen for milk as he can take milk from his own home. But Petya was a little bit bored to plan this time so he asked his brother to help him.

Now it is your job to help Petya Brother in finding out minimum cost needed to repair the roads in the above given way. If it is not possible for a citizen to connect to any of the milkmen, output "impossible" (without quotes).

PS: Note that you should print the minimum cost needed such that everyone can go to their nearest milkman.

Input

First line contains two space separated number n, m: number of citizens in Mayapur and m denotes number of unrepaired roads.

Next line contains n space integers either 0 or 1 which indices that citizen is milkmen or not[1 means he is a milkman]. (1 <= n <= 10^5)

Then For each of the next m lines, each line contains three space separated integers u, v and c, denoting that there exists a unrepaired road between u and v such that cost of repairing of road is c. (1 <= u, v <= n and u != v)

(1 <= m <= min (n * (n - 1) / 2, 2 * 10^5). 1 <= c <= 10^9.)

Output

Print the cost if not possible print "impossible".

Example

Input:
5 7
0 1 0 1 0
1 2 11
1 3 1
1 5 17
2 3 1
3 5 18
4 5 3
2 4 5

Output:
5

PS: for python users please make your submission using fastio or you can submit the solution into pypy.