题目描述

幸福国度可以用 $n$ 个城镇（用 $1$ 到 $n$ 编号）构成的集合来描述，这些城镇最开始由 $m$ 条双向道路（用 $1$ 到 $m$ 编号）连接。城镇 $1$ 是中央城镇。保证一个人从城镇 $1$ 出发，经过这些道路，可以到达其他的任何一个城市。这些道路都是收费道路，道路 $i$ 的使用者必须向道路的主人支付 $c_i$ 分钱的费用。已知所有的这些 $c_i$ 是互不相等的。最近有 $k$ 条新道路建成，这些道路都属于亿万富豪 Mr.Greedy。Mr.Greedy 可以决定每条新道路的费用（费用可以相同），并且他必须在明天宣布这些费用。

两周以后，幸福国度将举办一个盛况空前的嘉年华！大量的参与者将沿着这些道路游行并前往中央城镇。共计 $p_j$ 个参与者将从城镇 $j$ 出发前往中央城镇。这些人只会沿着一个选出的道路集合前行，并且这些选出的道路将在这件事的前一天公布。根据一个古老的习俗，这些道路将由幸福国度中最有钱的人选出，也就是 Mr.Greedy。同样根据这个习俗，Mr.Greedy 选出的这个道路集合必须使所有选出道路的费用之和最小，并且仍要保证任何人可以从城镇 $j$ 前往城镇 $1$（因此，这些选出的道路来自将费用作为相应边边权的 「最小生成树」）。如果有多个这样的道路集合，Mr.Greedy 可以选其中的任何一个，只要满足费用和是最小的。

Mr.Greedy 很明确地知道，他从 $k$ 条新道路中获得的收入不只是与费用有关。一条道路的收入等于所有经过这条路的人的花费之和。更准确地讲，如果 $p$ 个人经过道路 $i$，道路 $i$ 产生的收入为 $c_i \cdot p$ 的积。注意 Mr.Greedy 只能从新道路收取费用，因为原来的道路都不属于他。

Mr.Greedy 有一个阴谋。他计划通过操纵费用和道路的选择来最大化他的收入。他希望指定每条新道路的费用（将在明天公布），并且选择嘉年华用的道路（将在嘉年华的前一天公布），使得他在 $k$ 条新道路的收入最大。注意 Mr.Greedy 仍然需要遵循选出花费之和最小的道路集合的习俗。

你是一个记者，你想揭露他的计划。为了做成这件事，你必须先写一个程序 来确定 Mr.Greedy 可以通过他的阴谋获取多少收入。

输入格式

第一行包含三个由空格隔开的整数 $n$，$m$，$k$。

接下来的 $m$ 行描述最开始的 $m$ 条道路。这 $m$ 行中的第 $i$ 行包含由空格隔开的整数 $a_i$，$b_i$，$c_i$，表示有一条在 $a_i$ 和 $b_i$ 之间，费用为 $c_i$ 的双向道路。

接下来的 $k$ 行描述新建的 $k$ 条道路。这 $k$ 行中的第 $i$ 行包含由空格隔开的整数 $x_i$ 和 $y_i$，表示有一条连接城镇 $x_i$ 和 $y_i$ 的新道路。

最后一行包含 $n$ 个由空格隔开的整数，其中的第 $j$ 个为 $p_j$，表示从城镇 $j$ 前往城镇 $1$ 的人数。

输出格式

你的程序必须输出恰好一个整数到标准输出，表示能获得的最大的收入。

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

400

样例说明

在样例中，Mr.Greedy 应该将新道路 $(1,3)$ 的费用设置为 $5$ 分钱。

在这个费用下，他可以选择道路 $(3,5)$，$(1,2)$，$(2,4)$ 和 $(1,3)$ 来最小化总费用，这个费用为 $14$。从 城镇 $3$ 出发的 $30$ 个人和从 城镇 $5$ 出发的 $50$ 个人将经过新道路前往 城镇 $1$，因此他可以获得为$(30 + 50) \times 5=400$ 分钱的最好收入。

如果我们这样做，将新道路$(1,3)$的费用设置为 $10$ 分钱。根据传统的限制，Mr.Greedy必须选择 $(3,5)$，$(1,2)$，$(2,4)$ 和 $(2,3)$，因为这是唯一费用最小的集合。因此，在嘉年华的过程中道路 $(1,3)$ 将没有任何收入。

数据规模与约定

• 对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$1 \leq k \leq 20$，$1 \leq m \leq 3 \times 10^5$；
• 对每个 $i$ 和 $j$，$1 \leq c_i, p_j \leq 10^6$。