暂无测试数据。

题目描述

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

两周以后，
幸福国度将举办一个盛况空前的嘉年华！
大量的参与者将沿着这些道路游行并前往中央城镇。
共计个参与者将从城镇j出发前往中央城镇。
这些人只会沿着一个选出的道路集合前行，
并且这些选出的道路将在这件事的前一天公布。
根据一个古老的习俗，
这些道路将由幸福国度中最有钱的人选出，
也就是 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\) 条道路。
这 \(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 的人数。

输入也满足以下约束条件。

\(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\)；
如果 \(i \neq i'\) ，
则 \(c_i \neq c'_i\) ；
在任意两个城市之间，
最多只有一条道路（包括新建的道路）。

输出

一个整数，表示能获得的最大的收入。

样例输入

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

数据范围限制

我们将使用以下5类测例测试你的程序。

1.（国际16分，国内15分）\(N \leq 10\)，\(M \leq 20\) 且 \(K = 1\)；
2.（国际18分，国内20分）\(N \leq 30\)，\(M \leq 50\) 且 \(K \leq 10\)；
3.（国际22分，国内20分）\(N \leq 1,000\)，\(M \leq 5 \times 10^3\) 且 \(K \leq 10\)；
4.（国际22分，国内20分）\(N \leq 10^5\)，\(M \leq 3 \times 10^5\) 且 \(K \leq 15\)；
5.（国际22分，国内25分）\(N \leq 10^5\)，\(M \leq 3 \times 10^5\) 且 \(K \leq 20\)。

限制

每个测试点时限：2.5秒
内存限制：128MB

来源

APIO2013