21773_WateringHole

Farmer John has decided to bring water to his N (2 ≤ N ≤ 5,000) pastures which are conveniently numbered 1..N. And He has M (1 ≤ M ≤ 25,000) pipes. He may bring water to a pasture either by building a well in that pasture or connecting the pasture via a pipe to another pasture which already has water.

Digging a well in pasture i costs W_i (1 ≤ W_i ≤ 100,000). Connecting pastures i and j with a pipe costs p (1 ≤ p ≤ 100,000). Since the length and quality are different, there may be more than one pipes in different costs connecting pasture i and j.

Luckily, farmer John found there was only one plan to minimize his cost.

Farmer Jack, farmer John's friend, has P (1 ≤ P ≤ 1,000) pipes. He promised that he could give one pipe to Farmer John, and farmer John can use it to connect his pasture i and j. Now, farmer John wants to know how much the minimum amount he will have to pay to water all of his pastures if he chooses one more pipe from Jack.

There are serveral cases:

Line 1: Three integers: N, M and P

Lines 2: N space-separated integers; the i-th integer is W_i

Lines 3..M+3: Three integers: i, j, p. Means a pipe connecting pasture i and j costs p

Lines M+4..P+M+4: Two Integers: i, j. Farmer Jack can give Farmer John a pipe connecting pasture i and j.

Line 1..P: A single integer denoting the minimum cost of providing all the pastures with water if farmer John chooses the i-th pipe from farmer Jack.

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

7