In country P, there are $n$ villages and $m$ potential bidirectional roads to be built. The $i$-th road connects $u_i$ and $v_i$ with a construction cost of $w_i$.

The King has found $k$ guards. Each guard will be stationed in one village, and the $i$-th guard can only be stationed in a village belonging to the set $S_i$.

The King will assign each guard to a village and build some roads.

The King wants to ensure that the entire country is protected while minimizing costs. Therefore, he requires that every village can be reached by exactly one guard through a sequence of built roads.

The King wants to know if there exists a plan for building roads and assigning guards. If such a plan exists, what is the minimum total cost of building the roads?

Input

The first line contains three integers $n, m, k$, representing the number of villages, the number of roads, and the number of guards.

The next $m$ lines each contain three integers $u_i, v_i, w_i$, describing a road.

The next $k$ lines each contain $|S_i|+1$ integers. The first integer $|S_i|$ is the size of the set, followed by $|S_i|$ integers $s_{i,j}$ representing the contents of the set.

Output

Output a single integer. If a plan exists, output the minimum total cost; otherwise, output -1.

Examples

Input 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

Output 1

8

Note 1

Build roads $1, 2,$ and $6$. The two guards are stationed in villages $1$ and $4$, respectively.

Input 2

(See provided files)

Output 2

(See provided files)

Constraints

There are 20 test cases in total, each worth 5 points.

For all data, $1\leq n\leq 300$, $0\leq m\leq \frac{n(n-1)}{2}$, $1\leq k\leq n$, $1\leq w_i\leq 1000$.

For all data, it is guaranteed that $1\leq u_i < v_i\leq n$, $1\leq |S_i|\leq n$, $1\leq s_{i,j}\leq n$, $\forall i\neq j, (u_i,v_i)\neq (u_j, v_j)$, and $\forall x, i\neq j, s_{x,i}\neq s_{x,j}$.