Toll

Happyland is a country of $N$ towns numbered $1$ to $N$. Town $1$ is the capital. Initially the towns are connected by $M$ two-way roads numbered $1$ to $M$, and it is guaranteed that every town can reach town $1$ using these roads. Every road is a toll road: using road $i$ costs $c_i$ cents, paid to that road's owner. All $c_i$ are distinct.

Recently a billionaire, Mr. Greedy, finished building $K$ additional new roads, all of which he owns. He may set the toll of each new road to any positive integer he likes (the new tolls need not be distinct), and he must announce these tolls tomorrow.

Two weeks from now a huge carnival will take place. For each town $j$, exactly $p_j$ people will start at town $j$ and travel to the capital, town $1$. They may only use a set of selected roads, which is announced the day before the carnival. By tradition, the selected roads are chosen by the richest person in Happyland, Mr. Greedy. The same tradition requires the selected set to (a) still let everyone travel from every town to town $1$, and (b) have the minimum possible total toll among all such sets. In other words, the selected roads must form a minimum spanning tree, using the tolls as edge weights. When several sets tie for the minimum total, Mr. Greedy may pick any one of them.

Mr. Greedy earns money only from the new roads (he owns none of the old ones). The revenue from a road equals its toll multiplied by the number of people who walk along it: if road $i$ has toll $c_i$ and $p$ people use it, its revenue is $c_i \cdot p$.

Mr. Greedy wants to maximize his total revenue from the $K$ new roads by cleverly choosing the new tolls and, when the minimum-total set is not unique, by cleverly choosing the selected roads, while still obeying the tradition of minimum total toll. Determine the maximum total revenue he can obtain.

The first line contains three integers $N$, $M$, and $K$.

Each of the next $M$ lines contains three integers $a_i$, $b_i$, and $c_i$: old road $i$ connects towns $a_i$ and $b_i$ and has toll $c_i$.

Each of the next $K$ lines contains two integers $x_i$ and $y_i$: new road $i$ connects towns $x_i$ and $y_i$.

The last line contains $N$ integers $p_1, p_2, \dots, p_N$, where $p_j$ is the number of people starting from town $j$.

Constraints:

• $1 \le N \le 100000$
• $1 \le K \le 20$
• $1 \le M \le 300000$
• $1 \le c_i, p_j \le 10^6$
• All $c_i$ are distinct.
• Between any two towns there is at most one road (counting both old and new roads).
• Using only the old roads, every town can reach town $1$.

Print a single integer: the maximum total revenue Mr. Greedy can obtain.

In the situation shown above, Mr. Greedy should set the toll of the new road $(1,3)$ to $5$. With this toll he can select the roads $(3,5)$, $(1,2)$, $(2,4)$, and $(1,3)$, whose total toll is the minimum possible, $14$. The $30$ people from town $3$ and the $50$ people from town $5$ then cross the new road on their way to town $1$, so its revenue is $(30 + 50) \times 5 = 400$.

If instead he set the toll of $(1,3)$ to $10$, the tradition would force him to select $(3,5)$, $(1,2)$, $(2,4)$, and $(2,3)$, the only minimum-total set, and no one would use the new road, earning him nothing.