import heapq def main(): import sys input = sys.stdin.read data = input().split() ptr = 0 N = int(data[ptr]) ptr += 1 M = int(data[ptr]) ptr += 1 adj = [[] for _ in range(N + M + 2)] # Virtual nodes are N+1 to N+M for i in range(M): k = int(data[ptr]) c = int(data[ptr + 1]) s = list(map(int, data[ptr + 2:ptr + 2 + k])) ptr += 2 + k virtual_node = N + 1 + i # i starts from 0, virtual nodes start at N+1 for u in s: cost = (u + c + 1) // 2 adj[u].append((virtual_node, cost)) adj[virtual_node].append((u, cost)) # Dijkstra's algorithm INF = float('inf') dist = [INF] * (N + M + 2) dist[1] = 0 heap = [] heapq.heappush(heap, (0, 1)) while heap: d, u = heapq.heappop(heap) if d > dist[u]: continue for v, w in adj[u]: if dist[v] > d + w: dist[v] = d + w heapq.heappush(heap, (dist[v], v)) print(dist[N] if dist[N] != INF else -1) if __name__ == '__main__': main()