M. 重建罗马

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

罗马帝国可以是任何事物,处于任何时空,你甚至可以在桶装水里面找到罗马帝国。

(这部分图文与题意没有任何关系)

神圣罗马帝国有 个城市,有一天发生了大地震,所有城市之间的道路都被破坏了,目前没有任何两个城市能互相到达。

现在有 个修缮方案,每个修缮方案可以描述为 “以 的代价在城市 之间修建一条道路” ,如果实施这个方案,就会花费 的代价,在此之后 之间就会有一条直达道路,这意味此时着任何一个在城市 的人可以走到 ,反之亦然。元老院现在要从这些方案中选出若干个来执行。

就在大灾难过后,罗马国力衰退之时,邻国罗姆苏丹似乎正在谋划入侵。

罗马帝国有 个忠心耿耿的守卫,每个守卫有一个自己愿意前往驻扎的城市集合,元老院非常尊重这些守卫,所以每个守卫都会被任命一个驻扎城市,且没有任何一个守卫会不被分配任务。

所有守卫在到达驻地并实行了所有被要求执行的修缮方案后,守卫会在所有自己能够到达的城市巡逻,保护罗马人民。此处 能够到达 的定义为:从 出发,经过有限条修缮后的道路可以到达

头疼的是,这些守卫之间关系并不好,如果有任何一个守卫巡逻的时候碰了另一个守卫,他们就会打架。

为了防止这种情况发生,一个城市不能被多个守卫巡逻。但为了保卫居民的安全,每个城市都必须被至少一个守卫巡逻。

形式化地说,对于神圣罗马帝国中的每一座城市,在执行了选定的修缮方案并派遣守卫后,每座城市必须可以被恰好一名守卫巡逻。

请你为元老院找到最小花费的修缮方案,使得存在一种派遣守卫的方式满足上述条件。

输入格式

输入第一行包含三个整数 (, ) ,含义见题目描述。

接下来的 行,每行有三个整数 ,表示存在一种修缮方案花费 的代价使得 之间的道路被修好。

接下来的 行,给出每个守卫可以被派遣的城市。每行开始有一个整数 ,表示这名守卫愿意前往的城市数量,接下来 个互不相同且不小于 不大于 的整数,表示这名守卫愿意前往的城市标号。

输入中所有同一行的整数用空格隔开。

输出格式

输出一个整数,表示最小花费。

特别地,如果任何方案都无法满足条件,输出一个整数

样例

样例输入

5 6 2
1 2 1
1 3 4
2 4 2
2 5 5
3 4 7
4 5 3
2 1 2
2 2 4

样例输出

8