在一个王国中，国王想要通过部署守卫来保护他的公民。他招募了一些守卫，并为他们配备了重型盔甲，以抵御强盗、外国骑士和其他不法之徒。他的守卫虽然强悍，但遗憾的是，他们不太聪明，会攻击任何穿着盔甲的人，甚至包括彼此！

王国由若干个村庄组成，村庄之间由道路连接。所有的道路质量都很差。有些道路泥泞不堪，有些则有摇摇欲坠的桥梁。没有一条道路能支撑穿着全套盔甲的守卫。因此，国王必须决定改善哪些道路，以便他的守卫能够到达整个王国。道路是双向的。每名守卫只能被部署在王国中特定村庄子集里的某一个村庄。

国王需要最小化改善道路的成本，同时满足以下几个约束条件：

• 每一名守卫都必须被部署；不能有守卫被遗漏。
• 每一名守卫必须被部署在他们所属的村庄子集内。
• 每一个村庄必须恰好由一名守卫覆盖。如果两名守卫能够互相到达，他们就会打架。

请帮助国王确定在满足上述约束条件的前提下，改善王国道路所需的最小成本。

输入格式

输入的第一行包含三个整数 $n$ ($1 \le n \le 300$)，$r$ ($0 \le r \le \frac{n(n-1)}{2}$) 和 $g$ ($1 \le g \le n$)，其中 $n$ 是村庄的数量，$r$ 是道路的数量，$g$ 是守卫的数量。村庄编号为 $1$ 到 $n$。

接下来的 $r$ 行，每行包含三个整数 $a, b$ ($1 \le a < b \le n$) 和 $c$ ($1 \le c \le 1000$)。每行描述了村庄 $a$ 和村庄 $b$ 之间的一条道路，改善它的成本为 $c$。道路是双向的；守卫可以从 $a$ 到 $b$ 或从 $b$ 到 $a$。每对村庄之间最多只有一条道路。

接下来的 $g$ 行，每行以一个整数 $k$ ($1 \le k \le n$) 开头，随后包含 $k$ 个整数 $v$ ($1 \le v \le n$)。每行描述了某一名特定守卫可以被放置的村庄子集。这些子集可能会重叠。

输出格式

输出一个整数，表示国王为了使每个村庄恰好被一名守卫覆盖且所有守卫都被部署，所必须支付的最小改善道路成本。如果无法以满足所有约束条件的方式部署守卫，则输出 $-1$。

样例

样例输入 1

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

样例输出 1

8