W pewnym królestwie król pragnie chronić swoich obywateli poprzez rozmieszczenie strażników. Zrekrutował on pewną liczbę strażników i wyposażył ich w ciężkie zbroje dla ochrony przed bandytami, obcymi rycerzami i innymi niegodziwcami. Jego strażnicy są twardzi, ale niestety niezbyt bystrzy i będą atakować każdego, kto nosi zbroję, nawet siebie nawzajem!

Królestwo składa się z pewnej liczby wiosek połączonych drogami. Wszystkie drogi są słabej jakości. Niektóre są błotniste, inne mają chwiejne mosty. Żadna z nich nie jest w stanie utrzymać strażnika w pełnej zbroi. Dlatego król musi zdecydować, które drogi ulepszyć, aby jego strażnicy mogli dotrzeć do całego królestwa. Drogi są dwukierunkowe. Każdy strażnik może zostać rozmieszczony tylko w jednej wiosce z określonego podzbioru wiosek królestwa.

Król musi zminimalizować koszt ulepszenia dróg, spełniając jednocześnie kilka innych ograniczeń:

• Każdy strażnik musi zostać rozmieszczony; żaden nie może zostać pominięty.
• Każdy strażnik musi zostać rozmieszczony w swoim podzbiorze wiosek.
• Każda wioska musi być osiągalna przez dokładnie jednego strażnika. Jeśli dwóch strażników może do siebie dotrzeć, będą walczyć.

Pomóż królowi wyznaczyć minimalny koszt ulepszenia dróg w jego królestwie przy zachowaniu powyższych ograniczeń.

Wejście

Pierwsza linia wejścia zawiera trzy liczby całkowite $n$ ($1 \le n \le 300$), $r$ ($0 \le r \le \frac{n(n-1)}{2}$) oraz $g$ ($1 \le g \le n$), gdzie $n$ to liczba wiosek, $r$ to liczba dróg, a $g$ to liczba strażników. Wioski są ponumerowane od $1$ do $n$.

Każda z kolejnych $r$ linii zawiera trzy liczby całkowite $a$, $b$ ($1 \le a < b \le n$) oraz $c$ ($1 \le c \le 1000$). Każda linia opisuje drogę między wioską $a$ a wioską $b$, której koszt ulepszenia wynosi $c$. Drogi są dwukierunkowe; strażnik może przemieszczać się z $a$ do $b$ lub z $b$ do $a$. Każda para wiosek jest połączona co najwyżej jedną drogą.

Każda z kolejnych $g$ linii zaczyna się od liczby całkowitej $k$ ($1 \le k \le n$), a następnie zawiera $k$ liczb całkowitych $v$ ($1 \le v \le n$). Każda linia opisuje wioski wchodzące w skład podzbioru, w którym może zostać umieszczony dany strażnik. Podzbiory mogą się nakładać.

Wyjście

Wypisz pojedynczą liczbę całkowitą, która jest minimalnym kosztem, jaki król musi ponieść, aby ulepszyć wystarczającą liczbę dróg tak, aby każda wioska była osiągalna przez dokładnie jednego strażnika i każdy strażnik był rozmieszczony. Wypisz $-1$, jeśli nie jest możliwe rozmieszczenie strażników w sposób spełniający wszystkie ograniczenia.

Przykład

Wejście 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

Wyjście 1

8