ある王国で、王は警備員を配置して市民を守ろうとしている。王は数人の警備員を雇い、盗賊や外国の騎士、その他の悪党から身を守るために重装甲を装備させた。警備員は屈強だが、残念ながらあまり賢くはなく、鎧を着ている者を見れば誰であれ、たとえ仲間同士であっても攻撃してしまう！

王国はいくつかの村で構成されており、それらは道路で結ばれている。すべての道路は質が悪く、泥だらけの場所もあれば、壊れかけの橋もある。どの道路も重装甲の警備員を支えることができない。そのため、王は警備員が王国全体に行き渡るように、どの道路を改良するかを決定しなければならない。道路は双方向である。各警備員は、王国の一部の村の集合のうち、特定の村にのみ配置することができる。

王は、以下のいくつかの制約を満たしながら、道路の改良コストを最小化する必要がある。

• すべての警備員を配置しなければならない。一人も残してはならない。
• 各警備員は、配置可能な村の集合の中に配置されなければならない。
• すべての村は、ちょうど一人の警備員から到達可能でなければならない。もし二人の警備員が互いに到達可能であれば、彼らは戦ってしまう。

上記の制約を満たしながら、王国で道路を改良するために必要な最小コストを求めるのを手伝ってほしい。

入力

入力の最初の行には、3つの整数 $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$ 行の各行には、3つの整数 $a, b$ ($1 \le a < b \le n$) と $c$ ($1 \le c \le 1000$) が含まれる。各行は村 $a$ と村 $b$ を結ぶ道路を表し、改良コストは $c$ である。道路は双方向であり、警備員は $a$ から $b$ へ、または $b$ から $a$ へ移動できる。どの村のペアの間にも、道路は最大で1本しか存在しない。

続く $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