有 $n$ 座城市与连接它们的 $m$ 条无向道路，原图连通。恢复第 $i$ 条原有道路需要支付费用 $w_i$。

另有 $k$ 个可选乡镇。启用第 $j$ 个乡镇需要支付 $c_j$；启用后还可以支付 $a_{j,i}$，在该乡镇与城市 $i$ 之间修建一条道路。乡镇之间不能新建道路。你可以启用任意多个乡镇，也可以一个也不启用。

求使原有 $n$ 座城市彼此连通所需的最小总费用。

输入格式

第一行包含三个整数 $n,m,k$。

接下来 $m$ 行，每行包含 $u_i,v_i,w_i$，表示一条原有道路。最后给出 $k$ 行：第 $j$ 行包含 $c_j$ 和 $n$ 个数 $a_{j,1},a_{j,2},\dots,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 \leq n \leq 10^4$，$1 \leq m \leq 10^6$，$0 \leq k \leq 10$；
• 对于所有 $1 \leq i \leq m$，均有 $1 \leq u_i, v_i \leq n$，$u_i \neq v_i$ 且 $0 \leq w_i \leq 10^9$；
• 对于所有 $1 \leq j \leq k$，均有 $0 \leq c_j \leq 10^9$；
• 对于所有 $1 \leq j \leq k$，$1 \leq i \leq n$，均有 $0 \leq a_{j,i} \leq 10^9$；
• 任意两座原有的城市都能通过若干条原有的道路相互到达。

特殊性质 A：对于所有 $1 \leq j \leq k$，均有 $c_j = 0$ 且均存在 $1 \leq i \leq n$ 满足 $a_{j,i} = 0$。

来源与数据说明

原题页面。以上题意为重新整理的表述，规则、输入输出和约束与原题一致。本题使用独立生成的训练数据，原题测试点表仅说明原比赛范围与特殊性质，本包评分不复刻官方测试点分布。标准输入输出，不要求文件读写。