

Watering HoleTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 943 Accepted Submission(s): 212 Problem 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 spaceseparated integers; the ith 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 ith pipe from farmer Jack. Sample Input
Sample Output
Source  
