當前沒有測試資料。

本题暂未上传测试数据，目前仅供阅读与练习。

本站练习请使用标准输入/输出；原卷中的文件名仅作原始资料参考。

题目描述

C 国有 $n$ 座城市与 $m$ 条双向道路，任意两座城市都能通过原有道路相互到达。第 $i$ 条道路连接 $u_i,v_i$。地震破坏了所有道路，修复第 $i$ 条道路需要费用 $w_i$。

另外有 $k$ 个可进行城市化改造的乡镇。改造第 $j$ 个乡镇需要费用 $c_j$；改造完成后，可在该乡镇与原有城市之间新建任意若干条道路，其中连接原有城市 $i$ 的道路费用为 $a_{j,i}$。可以改造任意多个乡镇，也可以不改造任何乡镇。

求使原有的 $n$ 座城市两两连通的最小总费用。总费用包括选定乡镇的改造费、道路修复费和新建道路费。

输入格式

第一行三个整数 $n,m,k$。接下来 $m$ 行，每行 $u_i,v_i,w_i$。随后 $k$ 行，第 $j$ 行给出 $n+1$ 个非负整数 $c_j,a_{j,1},\ldots,a_{j,n}$。

输出格式

输出一个非负整数，表示使原有城市两两连通的最小费用。

样例 1

输入

4 4 2
1 4 6
2 3 7
4 2 5
4 3 4
1 1 8 2 4
100 1 3 2 4

输出

13

数据范围

$1\le n\le10^4$，$1\le m\le10^6$，$0\le k\le10$；$1\le u_i,v_i\le n$ 且 $u_i\ne v_i$；$0\le w_i,c_j,a_{j,i}\le10^9$。保证原有道路构成的图连通。

原卷完整题面

以下保留原卷的图示、完整样例解释、分档约束和特殊性质，便于核对。原卷中引用的外部样例文件未随本次题面上传。

下载原卷题面 PDF