#include using namespace std; #include using namespace atcoder; // input and output of modint istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); } istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); } template istream &operator>>(istream &is, static_modint &a) { long long v; is >> v; a = v; return is; } template ostream &operator<<(ostream &os, const static_modint &a) { return os << a.val(); } template istream &operator>>(istream &is, dynamic_modint &a) { long long v; is >> v; a = v; return is; } template ostream &operator<<(ostream &os, const dynamic_modint &a) { return os << a.val(); } #define rep_(i, a_, b_, a, b, ...) for (int i = (a), lim##i = (b); i < lim##i; ++i) #define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define drep_(i, a_, b_, a, b, ...) for (int i = (a)-1, lim##i = (b); i >= lim##i; --i) #define drep(i, ...) drep_(i, __VA_ARGS__, __VA_ARGS__, __VA_ARGS__, 0) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #ifdef LOCAL void debug_out() { cerr << endl; } template void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); } #define debug(...) cerr << 'L' << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define dump(x) cerr << 'L' << __LINE__ << " " << #x << " = " << (x) << endl #else #define debug(...) (void(0)) #define dump(x) (void(0)) #endif template using V = vector; using ll = long long; using ld = long double; using Vi = V; using VVi = V; using Vl = V; using VVl = V; using Vd = V; using VVd = V; using Vb = V; using VVb = V; template using priority_queue_rev = priority_queue, greater>; template vector make_vec(size_t n, T a) { return vector(n, a); } template auto make_vec(size_t n, Ts... ts) { return vector(n, make_vec(ts...)); } template inline int sz(const T &x) { return x.size(); } template inline bool chmin(T &a, const T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T &a, const T b) { if (a < b) { a = b; return true; } return false; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const pair &p) { os << '(' << p.first << ", " << p.second << ')'; return os; } template istream &operator>>(istream &is, array &v) { for (auto &e : v) is >> e; return is; } template ostream &operator<<(ostream &os, const array &v) { for (auto &e : v) os << e << ' '; return os; } template istream &operator>>(istream &is, vector &v) { for (auto &e : v) is >> e; return is; } template ostream &operator<<(ostream &os, const vector &v) { for (auto &e : v) os << e << ' '; return os; } template inline void deduplicate(vector &a) { sort(all(a)); a.erase(unique(all(a)), a.end()); } template inline int count_between(const vector &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r) inline ll ceil_div(const ll x, const ll y) { return (x+y-1) / y; } // ceil(x/y) inline int floor_log2(const ll x) { assert(x > 0); return 63-__builtin_clzll(x); } // floor(log2(x)) inline int ceil_log2(const ll x) { assert(x > 0); return (x == 1) ? 0 : 64-__builtin_clzll(x-1); } // ceil(log2(x)) inline int popcount(const ll x) { return __builtin_popcountll(x); } inline void fail() { cout << -1 << '\n'; exit(0); } struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; // const int INF = (1<<30) - 1; const ll INFll = (1ll<<60) - 1; // const ld EPS = 1e-10; // const ld PI = acos(-1.0); // using mint = modint998244353; // using mint = modint1000000007; // using mint = modint; // using Vm = V; using VVm = V; template struct edge { int v; T w; edge(int v, T w) : v(v), w(w) {} }; template using Graph = vector>>; template vector dijkstra(const Graph &G, int s) { int n = G.size(); const auto INF_T = numeric_limits::max() / 2 - 1; vector dist(n, INF_T); using PTi = pair; priority_queue, function> pq( [] (auto x, auto y) { return x.first > y.first; } ); dist[s] = 0; pq.emplace(dist[s], s); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (dist[u] < d) continue; for (auto &[v, w] : G[u]) if (chmin(dist[v], d + w)) pq.emplace(dist[v], v); } return dist; } ll solve() { int n, m; cin >> n >> m; Graph G(n); int N = n; rep(_, m) { int k, c; cin >> k >> c; auto id = make_vec(2, 0, 0); rep(i, k) { int s; cin >> s; --s; id[s&1].push_back(s); } G.resize(N+4); for (auto u : id[0]) { G[u].emplace_back(N, u/2); G[N+2].emplace_back(u, u/2); } for (auto u : id[1]) { G[u].emplace_back(N+1, u/2); G[N+3].emplace_back(u, u/2); } rep(i, 2) rep(j, 2) { int w = c+1; if (i + j) ++w; G[N+i].emplace_back(N+2+j, w); } N += 4; } auto dist = dijkstra(G, 0); ll ans = dist[n-1]; if (ans > INFll) ans = -1; return ans; } int main() { cout << solve() << '\n'; }