幸福国度可以用 $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$ 的双向道路。保证 $1 \leq a_i, b_i \leq N$。保证如果 $i \neq i'$，则 $c_i \neq c_{i'}$。

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

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

保证在任意两个城市之间，最多只有一条道路（包括新建的道路）。

输出格式

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

样例一

input

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

output

400

explanation

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 类测例测试你的程序。

对每个 $i$ 和 $j$，$1 \leq c_i, p_j \leq 10^6$。

1. （$16$ 分） $N \leq 10, M \leq 20$ 且 $K = 1$;
2. （$18$ 分） $N \leq 30, M \leq 50$ 且 $K \leq 10$;
3. （$22$ 分） $N \leq 1000, M \leq 5000$ 且 $K \leq 10$;
4. （$22$ 分） $N \leq 100000, M \leq 300000$ 且 $K \leq 15$;
5. （$22$ 分） $N \leq 100000, M \leq 300000$ 且 $K \leq 20$。

时间限制：$3\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载