En un cierto reino, el rey quiere proteger a sus ciudadanos desplegando guardias. Ha reclutado a varios guardias y los ha equipado con armaduras pesadas para protegerlos de bandidos, caballeros extranjeros y otros malhechores. Sus guardias son fuertes, pero desafortunadamente no son muy brillantes y atacarán a cualquiera que lleve armadura, ¡incluso entre ellos mismos!

El reino consta de varias aldeas conectadas por caminos. Todos los caminos son de mala calidad. Algunos son fangosos, otros tienen puentes destartalados. Ninguno de ellos puede soportar a un guardia con armadura completa. Por lo tanto, el rey debe decidir qué caminos mejorar para que sus guardias puedan llegar a todo el reino. Los caminos son bidireccionales. Cada guardia solo puede ser desplegado en una única aldea dentro de un subconjunto determinado de las aldeas del reino.

El rey necesita minimizar el costo de mejorar los caminos mientras satisface varias restricciones adicionales:

• Todos los guardias deben ser desplegados; ninguno debe quedar fuera.
• Cada guardia debe ser desplegado en su subconjunto de aldeas permitido.
• Cada aldea debe ser alcanzable por exactamente un guardia. Si dos guardias pueden alcanzarse entre sí, pelearán.

Ayude al rey a determinar el costo mínimo de mejorar los caminos de su reino mientras satisface las restricciones anteriores.

Entrada

La primera línea de la entrada contiene tres enteros $n$ ($1 \le n \le 300$), $r$ ($0 \le r \le \frac{n(n-1)}{2}$) y $g$ ($1 \le g \le n$), donde $n$ es el número de aldeas, $r$ es el número de caminos y $g$ es el número de guardias. Las aldeas están numeradas del 1 al $n$.

Cada una de las siguientes $r$ líneas contiene tres enteros $a$, $b$ ($1 \le a < b \le n$) y $c$ ($1 \le c \le 1000$). Cada línea describe un camino entre la aldea $a$ y la aldea $b$, con un costo de mejora de $c$. Los caminos son bidireccionales; un guardia puede ir de $a$ a $b$ o de $b$ a $a$. Cada par de aldeas tiene como máximo un camino entre ellas.

Cada una de las siguientes $g$ líneas comienza con un entero $k$ ($1 \le k \le n$), y luego contiene $k$ enteros $v$ ($1 \le v \le n$). Cada línea describe las aldeas que componen el subconjunto donde un guardia en particular puede ser colocado. Los subconjuntos pueden solaparse.

Salida

Imprima un único entero, que es el costo mínimo que el rey debe pagar para mejorar suficientes caminos de modo que cada aldea sea alcanzable por exactamente un guardia y cada guardia sea desplegado. Imprima $-1$ si no es posible desplegar a los guardias de una manera que satisfaga todas las restricciones.

Ejemplos

Entrada 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

Salida 1

8