#3206. [Apio2013]道路费用

题目描述

.jpg)

输入格式

第一行包含三个由空格隔开的整数N，M和K。

接下来的 M行描述最开始的M 条道路

这M行中的第i行包含由空格隔开的整数ai，bi和c i，表示有一条在a i和b i之间，费用为c i的双向道路。

接下来的K行描述新建的K条道路。

这 K行中的第i行包含由空格隔开的整数 xi和yi，表示有一条连接城镇xi和yi新道路

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

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

1 ≤ N ≤ 100000；1 ≤ K ≤ 20；1 ≤ M ≤ 300000；对每个i和j，1 ≤ ci, pj ≤ 10^6；

注意：边权值可能相同

输出格式

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

样例

样例输入

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)_5=400 分钱的最好收入。

如果我们这样做，将新道路(1,3)的费用设置为 10分钱。

根据传统的限制，Mr. Greedy必须选择(3,5)，(1,2)，(2,4)和(2,3)，因为这是唯一费用最小的集合

。因此，在嘉年华的过程中道路(1,3)将没有任何收入。