어느 왕국에서 왕은 경비병을 배치하여 시민들을 보호하고자 합니다. 왕은 여러 명의 경비병을 모집하여 도적, 외국 기사 및 기타 불량배들로부터 보호하기 위해 무거운 갑옷을 입혔습니다. 경비병들은 강인하지만 불행히도 머리가 좋지 않아 갑옷을 입은 사람이라면 누구든, 심지어 서로까지도 공격할 것입니다!

왕국은 도로로 연결된 여러 마을로 구성되어 있습니다. 모든 도로는 상태가 좋지 않습니다. 어떤 도로는 진흙투성이고, 어떤 도로는 낡은 다리가 있습니다. 그 어떤 도로도 완전 무장한 경비병을 지탱할 수 없습니다. 따라서 왕은 경비병들이 왕국 전체에 도달할 수 있도록 어떤 도로를 보수할지 결정해야 합니다. 도로는 양방향입니다. 각 경비병은 왕국 마을의 특정 부분 집합 내의 단일 마을에만 배치될 수 있습니다.

왕은 다음의 여러 제약 조건을 만족하면서 도로 보수 비용을 최소화해야 합니다.

• 모든 경비병은 배치되어야 하며, 빠지는 사람이 없어야 합니다.
• 모든 경비병은 자신이 배치될 수 있는 마을의 부분 집합 내에 배치되어야 합니다.
• 모든 마을은 정확히 한 명의 경비병에 의해 도달 가능해야 합니다. 만약 두 경비병이 서로 도달할 수 있다면, 그들은 싸우게 됩니다.

위의 제약 조건을 만족하면서 왕국 도로를 보수하는 최소 비용을 구할 수 있도록 왕을 도와주세요.

입력

입력의 첫 번째 줄에는 세 정수 $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