Happyland 可以被描述为一组 $N$ 个城镇（编号为 $1$ 到 $N$），最初由 $M$ 条双向道路（编号为 $1$ 到 $M$）连接。城镇 $1$ 是中心城镇。保证可以通过这些道路从城镇 $1$ 到达任何其他城镇。这些道路是收费道路。道路 $i$ 的使用者必须向道路所有者支付 $c_i$ 分的通行费。已知所有 $c_i$ 都是不同的。最近，新建成了 $K$ 条额外的道路，它们由亿万富翁 Mr. Greedy 拥有。Mr. Greedy 可以决定这些新道路的通行费（不一定不同），并且他必须在明天公布这些通行费。
两周后，Happyland 将举行一场盛大的嘉年华！大量的参与者将前往中心城镇并沿着道路游行。总共有 $p_j$ 名参与者将从城镇 $j$ 出发前往中心城镇。他们只会沿着一组选定的道路行驶，而选定的道路将在活动前一天公布。根据古老的传统，道路由 Happyland 最富有的人，即 Mr. Greedy 选择。受同一传统的约束，Mr. Greedy 必须选择一组道路，使得所选道路的通行费总和最小，同时允许任何人从城镇 $j$ 到达城镇 $1$（因此，所选道路构成一个“最小生成树”，其中通行费是相应边的权重）。如果存在多组这样的道路，只要通行费总和最小，Mr. Greedy 可以选择其中任何一组。
Mr. Greedy 非常清楚，他从 $K$ 条新道路中获得的收入不仅仅取决于通行费。道路的收入实际上是从沿该道路行驶的人那里收取的总费用。更准确地说，如果有 $p$ 个人沿着道路 $i$ 行驶，那么道路 $i$ 的收入就是乘积 $c_i p$。注意，Mr. Greedy 只能从新道路收取费用，因为他不拥有任何旧道路。
Mr. Greedy 有一个狡猾的计划。他计划通过操纵通行费和道路选择来最大化他在嘉年华期间的收入。他希望为新道路分配通行费（明天公布），并为嘉年华选择道路（嘉年华前一天公布），以最大化他从 $K$ 条新道路中获得的收入。注意，Mr. Greedy 仍然必须遵循选择通行费总和最小的道路集合的传统。
你是一名记者，想要揭露他的计划。为此，你必须首先编写一个程序来确定 Mr. Greedy 通过他的狡猾计划能获得多少收入。
输入格式
你的程序必须从标准输入读取数据。第一行包含三个空格分隔的整数 $N$、$M$ 和 $K$。接下来的 $M$ 行描述了最初的 $M$ 条道路。其中第 $i$ 行包含空格分隔的整数 $a_i$、$b_i$ 和 $c_i$，表示城镇 $a_i$ 和 $b_i$ 之间有一条通行费为 $c_i$ 的双向道路。接下来的 $K$ 行描述了新建的 $K$ 条额外道路。其中第 $i$ 行包含空格分隔的整数 $x_i$ 和 $y_i$，表示有一条连接城镇 $x_i$ 和 $y_i$ 的新道路。最后一行包含 $N$ 个空格分隔的整数，其中第 $j$ 个整数是 $p_j$，表示从城镇 $j$ 前往城镇 $1$ 的人数。
输入还满足以下约束条件：
- $1 \le N \le 100000$。
- $1 \le K \le 20$。
- $1 \le M \le 300000$。
- 对于每个 $i$ 和 $j$，$1 \le c_i, p_j \le 10^6$。
- 如果 $i \neq i'$，则 $c_i \neq c_{i'}$。
- 任意两个城镇之间最多只有一条道路（包括新建的道路）。
输出格式
你的程序必须向标准输出写入一个整数，即可以获得的最大总收入。
样例
样例输入 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
样例输出 1
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)$ 将不会收取任何收入。
子任务
你的程序将在 $5$ 组实例上进行测试，如下所示：
- (16 分) $N \le 10, M \le 20$ 且 $K = 1$。
- (18 分) $N \le 30, M \le 50$ 且 $K \le 10$。
- (22 分) $N \le 1,000, M \le 5,000$ 且 $K \le 10$。
- (22 分) $N \le 100,000, M \le 300,000$ 且 $K \le 15$。
- (22 分) $N \le 100,000, M \le 300,000$ 且 $K \le 20$。
Figure 1. 城镇和道路示意图