Trong một vương quốc nọ, nhà vua muốn bảo vệ thần dân của mình bằng cách triển khai các lính canh. Ông đã tuyển mộ một số lính canh và trang bị cho họ bộ giáp nặng để chống lại bọn cướp, các hiệp sĩ ngoại bang và những kẻ bất hảo khác. Lính canh của ông rất dũng mãnh, nhưng đáng tiếc là họ không được thông minh cho lắm và sẽ tấn công bất cứ ai mặc giáp, kể cả lẫn nhau!

Vương quốc bao gồm một số ngôi làng được kết nối với nhau bằng các con đường. Tất cả các con đường đều có chất lượng kém. Một số con đường bị lầy lội, một số khác có những cây cầu ọp ẹp. Không con đường nào có thể chịu được một lính canh mặc giáp đầy đủ. Vì vậy, nhà vua phải quyết định cải tạo những con đường nào để lính canh của mình có thể tiếp cận toàn bộ vương quốc. Các con đường là hai chiều. Mỗi lính canh chỉ có thể được triển khai tại một ngôi làng duy nhất trong một tập hợp con các ngôi làng của vương quốc.

Nhà vua cần tối thiểu hóa chi phí cải tạo đường sá trong khi vẫn phải thỏa mãn một số ràng buộc khác:

• Mọi lính canh phải được triển khai; không ai được phép bị bỏ lại.
• Mỗi lính canh phải được triển khai trong tập hợp con các ngôi làng cho phép của họ.
• Mỗi ngôi làng phải có thể tiếp cận được bởi đúng một lính canh. Nếu hai lính canh có thể tiếp cận lẫn nhau, họ sẽ đánh nhau.

Hãy giúp nhà vua xác định chi phí tối thiểu để cải tạo các con đường trong vương quốc của mình trong khi vẫn thỏa mãn các ràng buộc trên.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa ba số nguyên $n$ ($1 \le n \le 300$), $r$ ($0 \le r \le \frac{n(n-1)}{2}$) và $g$ ($1 \le g \le n$), trong đó $n$ là số ngôi làng, $r$ là số con đường và $g$ là số lính canh. Các ngôi làng được đánh số từ $1$ đến $n$.

Mỗi dòng trong số $r$ dòng tiếp theo chứa ba số nguyên $a, b$ ($1 \le a < b \le n$) và $c$ ($1 \le c \le 1000$). Mỗi dòng mô tả một con đường giữa ngôi làng $a$ và ngôi làng $b$, với chi phí cải tạo là $c$. Các con đường là hai chiều; một lính canh có thể đi từ $a$ đến $b$ hoặc từ $b$ đến $a$. Mỗi cặp ngôi làng có tối đa một con đường nối giữa chúng.

Mỗi dòng trong số $g$ dòng tiếp theo bắt đầu bằng một số nguyên $k$ ($1 \le k \le n$), và sau đó chứa $k$ số nguyên $v$ ($1 \le v \le n$). Mỗi dòng mô tả các ngôi làng tạo thành tập hợp con nơi một lính canh cụ thể có thể được đặt. Các tập hợp con có thể chồng lấn lên nhau.

Dữ liệu ra

In ra một số nguyên duy nhất là chi phí tối thiểu mà nhà vua phải trả để cải tạo đủ số đường sao cho mọi ngôi làng đều có thể tiếp cận được bởi đúng một lính canh, và mọi lính canh đều được triển khai. In ra $-1$ nếu không thể triển khai các lính canh theo cách thỏa mãn tất cả các ràng buộc.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

8