Connect the Country 2

Problem Statement

Connect the Country 2 Problem Description There are n cities, numbered 1 through n , and city i has an associated cost cost[i] . A bidirectional road may be built between any two different cities i and j . Its price is cost[i] + cost[j] . In addition there are m offers . Offer t is a triple (u, v, k) , meaning a road between cities u and v may instead be built for exactly k . For an offered pair you may use the offer price or the normal price, whichever you prefer. Find the minimum total price needed to make every city reachable from every other city. Input Format The first line contains the integer n . The second line contains n integers cost[1] ... cost[n] . The third line contains the integer m . Each of the next m lines contains three integers u , v and k . All integers may be separated by any whitespace, so the costs may also be split over several lines. Output Format Print a single integer: the minimum total price. Constraints 2 <= n <= 1500 0 <= m <= 1500 1 <= cos