Petya lives in a city named Mayapur. As in the morning, everybody likes to drink hot tea in bed. So the citizens of Mayapur need milk to produce tea. For this purpose, they want to be able to go to a milkman 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 was short of money last year, he repaired them such that with minimum budget everyone could get milk from someone. Since then he received some complaints that some people had 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 milkman does not need to go to some other milkman 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's Brother in finding the 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 numbers n and m: n is the number of citizens in Mayapur and m is the number of unrepaired roads.

Next line contains n space separated integers either 0 or 1 which indicates that citizen is milkman or not [1 means he is a milkman].

Then each of the next m lines contain three space separated integers u, v and c, denoting that there exists an unrepaired road between u and v such that the cost of repairing the road is c.

1 ≤ n ≤ 10⁵

1 ≤ m ≤ min(n * (n - 1) / 2, 2 * 10⁵)

1 ≤ u, v ≤ n and u ≠ v

1 ≤ c ≤ 10⁹

Output

Print the cost, or 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.