Problem Description
Mikoto(Railgun) is an excellent ESP(Extra Sensory Perception) girl with the dreadful skill Railgun in Academy City.
But there is a bitter reality that Mikoto's sisters are being massacred by Yuriko(Accelerator) for experiments.
As Yuriko is the most powerful ESPer, what Mikoto can do is to destroy all related laboratories in Academy City to delay the massacre.
N Laboratories are connected by M wires and the power system can be considered to an undirected graph.
Academy City is divided into several districts.
If there are at least two non-intersecting paths between two laboratories, then the two cities belong to the same district.
Two paths are considered as non-intersecting paths if and only if there is no same edge in both of them.
If there are one wire connecting two laboratories of two different districts, then the two districts are neighbors. Power can be transported between neighbor districts.
Mikoto can destroy all laboratories in the district where she is by the Railgun, that costs K+X(X is the numbers of laboratories in this district) points energy. Mikoto can use the Railgun anywhere and any number of times.
What's more, Mikoto generates electricity at the same time she shoot the Railgun. Mikoto can use the power to destroy all laboratories in other districts via wires. For any district to be attacked by electricity, the cost is f(n) points energy, and n is the number of districts (excluding the district where Mikoto shoot the Railgun) in the path from Mikoto to it. More specifically, if Mikoto have shot the Railgun destroying all laboratories in the district she chose, she can choose several other districts to be attacked by electricity she generate and the cost for each district is described above.
Now, the problem is the mininum cost to destroy all laboratories.
Input
There are several test cases.
For each test case, the first line contains three integers, N(1 ≤ N ≤ 1000), M(1 ≤ M ≤ 1000000), K(1 ≤ K ≤ 1000000000).
Then, 2 to M + 1 lines, each line contain two different integers a and b (1 ≤ a,b ≤ N), meaning that there is a undirected wire between laboratories a and b.
Then, the M + 2 lines contain N-1 number, meaning f(1), f(2), ... , f(n - 1). (0 ≤ f(1) ≤ f(2) ≤ ... ≤ f(N - 1) ≤ 1000000000)
You can safely assume that all numbers in the input and output will in the range of 32-bit signed integer and all the laboratories are connected by wires.
Input is terminated by EOF.
Output
For each test case, output one single number which is the mininum cost to destroy all laboratories.
Sample Input
5 5 10
1 2
1 3
2 3
1 4
2 5
5 10 15 20
5 4 10
2 1
3 2
4 1
5 3
4 9 11 12
Sample Output
23
34
