왕의 경비병

어느 왕국에서 왕은 경비병을 배치해 백성을 지키려 합니다. 왕은 경비병을 여러 명 모았고, 도적, 외국 기사, 그 밖의 무법자로부터 보호하도록 무거운 갑옷을 입혔습니다. 경비병은 튼튼하지만 머리가 그리 좋지 않아서, 갑옷을 입은 자라면 동료라도 공격합니다.

왕국은 도로로 연결된 여러 마을로 이루어져 있습니다. 모든 도로의 상태가 나쁩니다. 진흙탕 길도 있고, 삐걱거리는 다리가 놓인 길도 있습니다. 어느 도로도 갑옷을 입은 경비병을 지탱하지 못합니다. 그래서 왕은 경비병이 왕국 전체에 도달할 수 있도록 어느 도로를 개량할지 정해야 합니다. 도로는 양방향입니다. 각 경비병은 왕국 마을의 특정 부분집합에 속한 마을 한 곳에만 배치될 수 있습니다. 부분집합끼리는 겹칠 수 있습니다.

왕은 다음 조건을 지키면서 도로 개량 비용을 최소로 줄이려 합니다.

• 모든 경비병을 배치해야 합니다. 한 명도 빠뜨릴 수 없습니다.
• 각 경비병은 자신의 부분집합에 속한 마을에 배치해야 합니다.
• 모든 마을은 정확히 한 명의 경비병만 도달할 수 있어야 합니다. 두 경비병이 서로 도달할 수 있으면 둘은 싸웁니다.

모든 조건을 만족하는 도로 개량의 최소 비용을 구하세요.

첫 줄에 세 정수 $n$ ($1 \le n \le 300$), $r$ ($0 \le r \le \frac{n \cdot (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 1\,000$)가 주어집니다. 이는 마을 $a$와 $b$를 잇는 도로이며, 개량 비용은 $c$입니다. 도로는 양방향입니다. 두 마을 사이에는 도로가 최대 하나 있습니다.

이어지는 $g$개의 줄은 정수 $k$ ($1 \le k \le n$)로 시작하고, 뒤이어 $k$개의 정수 $v$ ($1 \le v \le n$)가 나옵니다. 한 경비병을 배치할 수 있는 마을의 목록입니다. 부분집합끼리는 겹칠 수 있습니다.

정수 하나를 출력합니다. 모든 마을이 정확히 한 명의 경비병에게만 도달되고 모든 경비병이 배치되도록 도로를 개량하는 최소 비용입니다. 모든 조건을 만족하는 배치가 불가능하면 $-1$을 출력합니다.