Watering Hole

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2887
64-bit integer IO format: %I64d      Java class name: Main

Description

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.

Input

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.

Output

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.

Sample Input

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

Sample Output

7

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .