题目描述

在 P 国有 $n$ 个村子，以及 $m$ 条待修建的双向公路，第 $i$ 条公路连接 $u_i$ 和 $v_i$，修建的代价为 $w_i$。

国王找到了 $k$ 个守卫，每个守卫将入驻一个村子，第 $i$ 个守卫能入驻的村子是集合 $S_i$。

国王将派遣每个守卫去一个村子，并修建一些公路。

国王希望整个国家得到保护的同时，尽可能节省开支。因此他希望每个村子可以被恰好一个守卫经过若干条公路到达。

国王想要知道，是否存在一种修建公路和派遣守卫的方案，如果存在，修建公路的代价之和最小是多少。

输入格式

第一行三个整数 $n,m,k$，表示村子个数，公路条数和守卫个数。

接下来 $m$ 行每行三个整数 $u_i, v_i, w_i$ 描述了一条公路。

接下来 $k$ 行，每行 $|S_i|+1$ 个整数，第一个整数 $|S_i|$ 表示集合大小，接下来 $|S_i|$ 个整数 $s_{i,j}$ 表示集合内容。

输出格式

一行一个整数，如果存在方案输出最小的代价之和，否则输出 -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

8

explanation

修建第 $1,2,6$ 条道路，两个守卫分别入驻 $1,4$ 号村子。

样例二

见附件

数据范围与提示

本题共 $20$ 组测试点，各 $5$ 分。

对于所有数据，$1\leq n\leq 300$，$0\leq m\leq \frac{n(n-1)}{2}$，$1\leq k\leq n$，$1\leq w_i\leq 1000$。

对于所有数据，保证 $1\leq u_i\lt v_i\leq n$，$1\leq |S_i|\leq n$，$1\leq s_{i,j}\leq n$，$\forall i\neq j, (u_i,v_i)\neq (u_j, v_j)$，$\forall x,i\neq j, s_{x,i}\neq s_{x,j}$。