Mr. Greedy's Carnival Revenue Maximization

Problem Statement

The Kingdom of Happiness is composed of N towns (numbered from 1 to N) connected by M bidirectional toll roads (numbered from 1 to M). Town 1 is the central town. It is guaranteed that starting from town 1 one can reach any other town using these roads. Each original road i has a toll cost of c_i cents; all c_i are distinct.

Recently, K new roads have been built by the billionaire Mr. Greedy. He can decide the toll fee for each new road (fees may be equal) and must announce them tomorrow.

Two weeks later, a grand carnival will be held in the Kingdom. A total of p_j participants will start from town j to travel to the central town (town 1) via a set of roads. However, the set of roads to be used will be announced only the day before the carnival. According to an ancient custom, the set of roads is chosen by the richest person of the Kingdom – Mr. Greedy. In keeping with the custom, the chosen road set must:

• Connect every town j to town 1 (i.e. form a spanning tree).
• Have the minimum possible total toll cost (i.e. be a minimum spanning tree under the given toll fees).

If there are several such spanning trees, Mr. Greedy may choose any one of them. Note that Mr. Greedy can only collect revenue from new roads; the original roads belong to others.

The revenue on any road is defined as (toll fee) × (number of participants that pass through the road). For a new road, if p people pass through it and its fee is set to c, the revenue will be c × p cents.

Mr. Greedy has a devious plan. By choosing the fees on his K new roads and, in the event of multiple MSTs, selecting one that maximizes his revenue, he wants to maximize the total revenue he collects from his new roads. As a journalist determined to expose his plan, your task is to compute the maximum total revenue Mr. Greedy can obtain.

How Mr. Greedy May Achieve This

The original roads, with distinct fees, have a unique MST (denote it by T₀). Mr. Greedy may try to replace some of the original roads in T₀ by one of his new roads while keeping the total cost unchanged. Specifically, consider a new road connecting towns u and v. When added to T₀, a unique cycle is formed. Let the maximum fee among the original roads on that cycle be W. If Mr. Greedy sets the fee of his new road to exactly W, then by replacing that maximum‐fee original road with his new road the total cost remains the same, and the new road can be included in an MST. The revenue from that new road will then be W × f where f is the number of participants who have to pass through the road on their way to town 1. In the MST the revenue on an edge is determined by the sum of p_j in the subtree not containing town 1 when that edge is removed.

Since Mr. Greedy can choose the MST arbitrarily among those whose total cost equals that of T₀, he can decide, for each new road, which original edge to replace – but note that each original edge may be replaced at most once. Hence, his problem reduces to selecting a set of new roads and assigning each one an original edge e (lying on the unique path between its endpoints in T₀) so as to maximize the sum:

\(\displaystyle \sum_{\text{new road } i} cost(e_i) \times load(e_i)\)

where cost(e_i) is the toll fee of the replaced original road (which is the maximum allowable fee for the new road to still be used in an MST) and load(e_i) is the number of participants that would traverse the edge if it were in the MST. Formulate and solve this optimization problem.

Input Format

The input begins with three integers N, M and K (N towns, M original roads, and K new roads).

Then follow M lines each with three integers u v c describing an original road connecting towns u and v with cost c cents. All c are distinct.

The next line contains N integers: p₁, p₂, ..., p_N where p_j is the number of participants starting from town j (note that town 1 is the destination).

Then follow K lines, each with two integers u v representing a new road built by Mr. Greedy connecting towns u and v.

Output Format

Output a single integer: the maximum total revenue (in cents) that Mr. Greedy can obtain.

inputFormat

The first line contains three integers N, M and K (1 ≤ N, M, K ≤ some reasonable limit).
Each of the next M lines contains three integers u v c (1 ≤ u, v ≤ N; c are distinct positive integers).
The next line contains N integers: p₁, p₂, ..., p_N (non‐negative integers).
Each of the next K lines contains two integers u v (1 ≤ u, v ≤ N) representing a new road.

outputFormat

A single integer representing the maximum total revenue Mr. Greedy can collect (in cents).

sample

4 4 2
1 2 3
2 3 5
2 4 2
3 4 6
10 20 30 40
1 3
3 4

420