1175: [CSP-S 2025] T2 道路修复 / road
Description
然而，近期由于一场大地震，所有 m 条道路都被破坏了，修复第 i（1 ≤ i ≤ m）条道路的费用为 wi。与此同时，C 国还有 k 个准备进行城市化改造的乡镇。对于第 j（1 ≤ j ≤ k）个乡镇，C 国对其进行城市化改造的费用为 cj。在城市化改造完第 j（1 ≤ j ≤ k）个乡镇后，可以在这个乡镇与原来的 n 座城市间建造若干条道路，其中在它与第 i（1 ≤ i ≤ n）座城市间建造一条道路的费用为 aj,i。C 国可以在这 k 个乡镇中选择任意多个进行城市化改造，也可以不选择任何乡镇进行城市化改造。
为尽快恢复城市间的交通，C 国政府希望以最低的费用将原有的 n 座城市两两连通，也即任意两座原有的城市都能通过若干条修复或新建造的道路相互到达。你需要帮助他们求出，将原有的 n 座城市两两连通的最小费用。
Input
输入的第一行包含三个非负整数 n, m, k，分别表示原有的城市数量、道路数量和准备进行城市化改造的乡镇数量。
输入的第 i+1（1 ≤ i ≤ m）行包含三个非负整数 ui,
vi, wi，表示第 i 条道路连接的两座城市与修复该道路的费用。
输入的第 j+m+1（1 ≤ j ≤ k）行包含 n+1 个非负整数 cj, aj,1, aj,2, …, aj,n，分别表示将第 j 个乡镇进行城市化改造的费用与在该乡镇与原有的城市间建造道路的费用。
Output
输出一行一个非负整数，表示将原有的 n 座城市两两连通的最小费用。
Sample Input Copy
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
Sample Output Copy
13HINT
【样例 1 解释】
C 国政府可以选择修复第 3 条和第 4 条道路，然后将第 1 个乡镇进行城市化改造，并建造它与第
1,3 座城市间的道路，总费用为 5 + 4 + 1 + 1 + 2 = 13。可以证明，不存在比 13 更小的费用能使原有的 4 座城市两两连通。
【样例 2】
见选手目录下的
road/road2.in 与
road/road2.ans。
该样例满足测试点 11,12 的约束条件。
【样例 3】
见选手目录下的
road/road3.in 与
road/road3.ans。
该样例满足测试点 13,14 的约束条件。
【样例 4】
见选手目录下的
road/road4.in 与
road/road4.ans。
该样例满足测试点 15,16 的约束条件。
【数据范围】
对于所有测试数据，保证：
- 1 ≤ n ≤ 104，1 ≤ m ≤ 106，0 ≤ k ≤ 10；
- 对于所有 1 ≤ i ≤ m，均有 1 ≤ ui, vi ≤ n, ui ≠ vi 且 0 ≤ wi ≤ 109；
- 对于所有 1 ≤ j ≤ k，均有 0 ≤ cj ≤ 109；
- 对于所有 1 ≤ j ≤ k，1 ≤ i ≤ n，均有 0 ≤ aj,i ≤ 109；
- 任意两座原有的城市都能通过若干条原有的道路相互到达。
|
测试点编号
|
n ≤
|
m ≤
|
k ≤
|
特殊性质
|
|
1 ~ 4
|
104
|
106
|
0
|
无
|
|
5, 6
|
103
|
105
|
5
|
A
|
|
7, 8
|
^
|
^
|
^
|
无
|
|
9, 10
|
^
|
106
|
^
|
A
|
|
11, 12
|
^
|
^
|
^
|
无
|
|
13, 14
|
^
|
^
|
10
|
A
|
|
15, 16
|
^
|
^
|
^
|
无
|
|
17, 18
|
104
|
^
|
5
|
A
|
|
19, 20
|
^
|
^
|
^
|
无
|
|
21 ~ 25
|
^
|
^
|
10
|
^
|
特殊性质 A：对于所有 1 ≤ j ≤ k，均有 cj =
0 且均存在 1 ≤ i ≤ n 满足 aj,i =
0。