#include <algorithm>
#include <fstream>
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
using namespace std;

ifstream fin("boom.in");
ofstream fout("boom.out");

const int MAX_N = 20;
const int MAX_M = 50;
const int INF = 1 << 30;

priority_queue<pair<int, int>> heap;
pair<int, int> back_info[(1 << MAX_N)];
vector<bool> visited(1 << MAX_N);
vector<int> d(1 << MAX_N, INF);
int strike[MAX_M];
int strike_cost[MAX_M];
int N, M;
int SOURCE, DESTINATION;

void read_input();
void solve();
void print_output();
void dijkstra();

int main() {
  read_input();
  dijkstra();
  print_output();
  return 0;
}

void read_input() {
  fin >> N >> M;
  for (int i = 0, strike_size; i < M; ++i) {
    fin >> strike_cost[i] >> strike_size;
    strike[i] = (1 << N) - 1;
    for (int j = 0, pos; j < strike_size; ++j) {
      fin >> pos;
      strike[i] ^= (1 << (pos - 1));
    }
  }
  SOURCE = (1 << N) - 1;
  DESTINATION = 0;
}

void print_output() {
  stack<int> solution;
  for (int node = DESTINATION; node != SOURCE; node = back_info[node].first) {
    solution.push(back_info[node].second);
  }
  fout << d[DESTINATION] << '\n';
  fout << solution.size() << '\n';
  while (!solution.empty()) {
    fout << solution.top() + 1 << '\n';
    solution.pop();
  }
}

void dijkstra() {
  heap.push(make_pair(0, SOURCE));
  d[SOURCE] = 0;

  while (!heap.empty()) {
    int node = heap.top().second;
    heap.pop();
    
    if (node == 0) break;
    if (visited[node]) continue;
    visited[node] = true;

    for (int j = 0, neighbour; j < M; ++j) {
      neighbour = node & strike[j];
      neighbour = (neighbour << 1) | (neighbour >> 1);
      if (neighbour >= (1 << N)) neighbour -= (1 << N);

      if (d[node] + strike_cost[j] < d[neighbour]) {
        d[neighbour] = d[node] + strike_cost[j];
        heap.push(make_pair(-d[neighbour], neighbour));
        back_info[neighbour] = make_pair(node, j);
      }
    }
  }
}