В некотором королевстве король хочет защитить своих граждан, расставив стражников. Он набрал некоторое количество стражников и одел их в тяжелые доспехи для защиты от бандитов, иностранных рыцарей и прочих негодяев. Его стражники сильны, но, к сожалению, не очень умны и будут атаковать любого, кто носит доспехи, даже друг друга!

Королевство состоит из нескольких деревень, соединенных дорогами. Все дороги находятся в плохом состоянии. Некоторые из них грязные, на других — ветхие мосты. Ни одна из них не выдержит стражника в полном доспехе. Поэтому король должен решить, какие дороги улучшить, чтобы его стражники могли добраться до любой точки королевства. Дороги двусторонние. Каждый стражник может быть размещен только в одной деревне из определенного подмножества деревень королевства.

Королю необходимо минимизировать стоимость улучшения дорог, соблюдая при этом несколько других ограничений:

• Каждый стражник должен быть размещен; никто не должен остаться без дела.
• Каждый стражник должен быть размещен в деревне из своего подмножества.
• Каждая деревня должна быть достижима ровно для одного стражника. Если два стражника могут добраться друг до друга, они начнут сражаться.

Помогите королю определить минимальную стоимость улучшения дорог в его королевстве, при которой выполняются вышеуказанные ограничения.

Входные данные

Первая строка входных данных содержит три целых числа $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

8