Dans un certain royaume, le roi souhaite protéger ses citoyens en déployant des gardes. Il a recruté un certain nombre de gardes et les a équipés d'une armure lourde pour les protéger des bandits, des chevaliers étrangers et d'autres malfaiteurs. Ses gardes sont robustes, mais malheureusement, ils ne sont pas très intelligents et attaqueront quiconque porte une armure, même entre eux !

Le royaume se compose d'un certain nombre de villages, reliés par des routes. Toutes les routes sont de mauvaise qualité. Certaines sont boueuses, d'autres ont des ponts délabrés. Aucune ne peut supporter un garde en armure complète. Le roi doit donc décider quelles routes améliorer afin que ses gardes puissent atteindre tout le royaume. Les routes sont bidirectionnelles. Chaque garde ne peut être déployé que dans un seul village appartenant à un sous-ensemble spécifique des villages du royaume.

Le roi doit minimiser le coût de l'amélioration des routes tout en respectant plusieurs autres contraintes :

• Chaque garde doit être déployé ; aucun ne doit être laissé de côté.
• Chaque garde doit être déployé dans son sous-ensemble de villages autorisé.
• Chaque village doit être accessible par exactement un garde. Si deux gardes peuvent s'atteindre, ils se battront.

Aidez le roi à déterminer le coût minimum pour améliorer les routes de son royaume tout en satisfaisant les contraintes ci-dessus.

Entrée

La première ligne de l'entrée contient trois entiers $n$ ($1 \le n \le 300$), $r$ ($0 \le r \le \frac{n(n-1)}{2}$) et $g$ ($1 \le g \le n$), où $n$ est le nombre de villages, $r$ est le nombre de routes et $g$ est le nombre de gardes. Les villages sont numérotés de $1$ à $n$.

Chacune des $r$ lignes suivantes contient trois entiers $a$, $b$ ($1 \le a < b \le n$) et $c$ ($1 \le c \le 1\,000$). Chaque ligne décrit une route entre le village $a$ et le village $b$, coûtant $c$ à améliorer. Les routes sont bidirectionnelles ; un garde peut aller de $a$ à $b$ ou de $b$ à $a$. Chaque paire de villages possède au plus une route entre eux.

Chacune des $g$ lignes suivantes commence par un entier $k$ ($1 \le k \le n$), suivi de $k$ entiers $v$ ($1 \le v \le n$). Chaque ligne décrit les villages constituant le sous-ensemble où un garde particulier peut être placé. Les sous-ensembles peuvent se chevaucher.

Sortie

Affichez un seul entier, qui est le coût minimum que le roi doit payer pour améliorer suffisamment de routes afin que chaque village soit accessible par exactement un garde, et que chaque garde soit déployé. Affichez $-1$ s'il n'est pas possible de déployer les gardes d'une manière qui satisfasse toutes les contraintes.

Exemples

Entrée 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

Sortie 1

8