Galactik Football Solution

Problem

It's Galactik Football time! The Galactik Football Assosiation (GFA) has announced a football tournament between all the teams of all the planets in the galaxy.

Each planet of the galaxy has a government. Some governments have a mutual agreement between them. If planet $A$ has mutual agreement with planet $B$, then there is a bidirectional spaceway between $A$ and $B$, using which anybody can go from $A$ to $B$ and vice-versa. People can use these spaceways to travel from one planet to another, if there exists a path between them using some of the spaceways.

Each planet has its own football ground. The GFA has planned the matches in such a way that a team can have a match at any of these grounds. The GFA has come across some problems in the execution of their plan. They have found out that there are many pairs of planets between which there does not exist any path, so the football team of one of those planets can't reach the other planet. They requested the corresponding governments to make a spaceway between them, but they can’t because of the absence of a mutual agreement. So the GFA suggested that they will make teleportation devices between some pairs of planets which will be used only by the football teams to travel.

But there are two types of governments in the galaxy

1. Some of the governments are greedy and they want to make money through the GFA. Each of these government has asked the GFA for a tax value which it has to pay if it wants to make a teleport ending at their planet.
2. Others want to sponsor the event, so they will give money to the GFA if they make a teleport ending at their planet. The GFA would always avoid such governments no matter what the consequences are, because these kind of governments always have some dirty plans up their sleeves.

Now, the GFA wants to make bi-directional teleports between planets such that the football teams of any planet can reach any other planet to play a football match, using spaceways between the planets and/or teleports made by the GFA.

The GFA also has financial problems and want to spend as little money as possible. They have come to you so that you can help them calculate the minimum amount of money needed to fulfil their plan.

Input

• The first line of the input consists of two space separated integers - $N$ and $M$. $N$ is the number of planets and $M$ is the number of spaceways. The description of the spaceways follows.
• The next $M$ lines, each contain two space separated integers $A$ and $B$, denoting a mutual agreement and hence a spaceway to travel, between planet $A$ and planet $B$.
• The next $N$ lines each contain a single integer, the integer on the $i^{th}$ line representing $C_i$. If $C_i \geq 0$, then it represents the tax value which the GFA has to pay to the government of planet $i$ (it's a type $1$ government). If $C_i < 0$, then it represents the money that the $i^{th}$ government will pay to the GFA (it's a type $2$ government).

Output

Print the minimum amount needed for the GFA to fulfil their plan. If there is no way to do so, print "-1" (without quotes).

Constraints

• $1 \leq N \leq 10^5$
• $0 \leq M \leq 10^6$
• $0 \leq |C| \leq 10^4$
• $1 \leq A,B \leq N$
• $A \neq B$

Sample 1:

Input

Output

6 6
1 2
2 3
1 3
4 5
5 6
4 6
1
3
5
2
4
6

3

Sample 2:

Input

Output

3 1
2 3
1
-1
-1

-1

Program :

 #include <stdio.h>

#define NMAX 100100

#define INF 1000000000

int parent[NMAX], cmin[NMAX], size[NMAX];

int N, M, C, nike , i, j, k, sum, Cmin;

int Find(int x) 

{

int tx, rx;

tx = x;

while (parent[tx] > 0)

tx = parent[tx];

while (x != tx) 

{

rx = parent[x];

parent[x] = tx;

x = rx;

}

return tx;

}

void Union(int i, int j) 

{

int ti = Find(i), tj = Find(j);

if (ti == tj)

return;

nike--;

if (size[ti] >= size[tj]) 

{

parent[tj] = ti;

size[ti] += size[tj];

} 

else 

{

parent[ti] = tj;

size[tj] += size[ti];

}

}

int main() {

//freopen("x.txt", "r", stdin);

scanf("%d %d", &N, &M);

nike = N;

for (i = 1; i <= N; i++) 

{

cmin[i] = -1;

parent[i] = 0;

size[i] = 1;

}

for (k = 1; k <= M; k++) 

{

scanf("%d %d", &i, &j);

Union(i, j);

}

if (nike == 1) 

{

printf("0\n");

return 0;

}

for (i = 1; i <= N; i++) 

{

scanf("%d", &C);

if (C < 0)

continue;

j = Find(i);

if (cmin[j] < 0 || C < cmin[j])

cmin[j] = C;

}

sum = 0;

Cmin = INF;

for (i = 1; i <= N; i++) 

{

if (parent[i] > 0)

continue;

if (cmin[i] < 0) 

{

printf("-1\n");

return 0;

}

sum += cmin[i];

if (cmin[i] < Cmin)

Cmin = cmin[i];

}

printf("%d\n", sum + (nike - 2) * Cmin);

return 0;

}