在 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`。 ### 样例一 #### input
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
#### output
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}$。 | 测试点编号 | 特殊性质 | | :---------: | :------------------: | | $1\sim 2$ | $n\le 6$ | | $3\sim 4$ | $S_i$ 的大小均为 $1$ | | $5\sim 9$ | $w_i=1$ | | $10\sim 14$ | 公路不可能修建出环 | | $15\sim 20$ | $ $ | **时间限制:$\texttt{2s}$** **空间限制:$\texttt{512MB}$**