Assembling the Salty Fish Tree

MloVtry has obtained a salted fish tree with \(n\) vertices by burying half of himself. Unfortunately, the tree is incomplete, having broken into \(m\) edges. Each edge not only has a cost associated with connecting its two endpoints but also comes with a special vertex set \(S\). An edge can be added to the tree only if all vertices in its associated set \(S\) have already been connected in some component \(T\) before the edge is introduced.

Your task is to help MloVtry determine the minimum total cost required to assemble a spanning tree connecting all \(n\) vertices under these constraints. If it is impossible to construct such a spanning tree, print \(-1\).

Note: An edge with an empty set \(S\) (i.e. \(S=\emptyset\)) can always be used. When connecting two vertices \(u\) and \(v\) with an edge and associated set \(S\), the edge is allowed if and only if either the connected component containing \(u\) or the one containing \(v\) already includes all vertices in \(S\).

Input/Output Format: See below.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n \leq \text{small},\; 0 \leq m)\), representing the number of vertices and the number of available edges respectively.

Each of the following \(m\) lines describes an edge with the format:

 u v w k s1 s2 ... sk

Here, \(u\) and \(v\) (\(1 \le u,v \le n\)) are the endpoints, \(w\) is the cost to use this edge, \(k\) is the number of vertices in the special set \(S\), followed by \(k\) integers denoting the vertices in \(S\). (Vertices are 1-indexed.)

outputFormat

Output a single integer representing the minimum total cost to assemble the spanning tree under the given restrictions. If it is impossible to construct such a spanning tree, output \(-1\).

sample

4 3
1 2 3 0
2 3 4 0
3 4 5 0

12