Bitville is a seaside city that has a number of shopping centers connected by bidirectional roads, each of which has a travel time associated with it.  Each of the shopping centers may have a fishmonger who sells one or more kinds of fish.  Two cats, Big Cat and Little Cat, are at shopping center $\mbox{1}$ (each of the centers is numbered consecutively from $\mbox{1}$ to $n$).  They have a list of fish they want to purchase, and to save time, they will divide the list between them.  Determine the total travel time for the cats to purchase all of the types of fish, finally meeting at shopping center $n$.  Their paths may intersect, they may backtrack through shopping center $n$, and one may arrive at a different time than the other.  The minimum time to determine is when both have arrived at the destination.  

For example, there are $n=5$ shopping centers selling $k=3$ types of fish.  The following is a graph that shows a possible layout of the shopping centers connected by $m=4$ paths.  Each of the centers is labeled $\textbf{center number/fish types offered/cat(s)}\ \textbf{that visit(s)}$.  Here $\mbox{B}$ and $\boldsymbol{\mbox{L}}$ represent Big Cat and Little Cat, respectively.  In this example, both cats take the same path, i.e. $1\rightarrow3\rightarrow5$ and arrive at time $15+5=20$ having purchased all three types of fish they want.  Neither cat visits shopping centers $2$ or $4$.  

Function Description  

Complete the shop function in the editor below.  It should return an integer that represents the minimum time required for their shopping.  

shop has the following parameters: 

- n: an integer, the number of shopping centers 

- k: an integer, the number of types of fish 

- centers: an array of strings of space-separated integers where the first integer of each element is the number of types of fish sold at a center and the remainder are the types sold 

- roads: a 2-dimensional array of integers where the first two values are the shopping centers connected by the bi-directional road, and the third is the travel time for that road  

Input Format

The first line contains $3$ space-separated integers: $n$ (the number of shopping centers), $m$ (the number of roads), and $\boldsymbol{\mbox{k}}$ (the number of types of fish sold in Bitville), respectively.        

Each line $\boldsymbol{i}$ of the $n$ subsequent lines ($1\leq i\leq n$) describes a shopping center as a line of space-separated integers. Each line takes the following form:

The first integer, $t\left[i\right]$, denotes the number of types of fish that are sold by the fishmonger at the $i^{\mbox{th}}$ shopping center.
Each of the $t\left[i\right]$ subsequent integers on the line describes a type of fish sold by that fishmonger, denoted by $A[i][z]$, where $1\leq z\leq t[i]$ going forward.

Each line $j$ of the $m$ subsequent lines ($1\leq j\leq m$) contains $3$ space-separated integers that describe a road. The first two integers, $u[j]$ and $v[j]$, describe the two shopping centers it connects. The third integer, $w[j]$, denotes the amount of time it takes to travel the road.

Constraints

$2\leq n\leq10^3$
$1\leq m\leq2\times10^3$
$1\leq k\leq10$
$0\leq t[i]\leq k$
$1\leq A[i][z]\leq k$
All $A[i][z]$ are different for every fixed $\boldsymbol{i}$.
$1\leq u[j],v[j]\leq N$
$1\leq w[j]\leq10^4$
Each road connectes $2$ distinct shopping centers (i.e., no road connects a shopping center to itself).
Each pair of shopping centers is directly connected by no more than $\mbox{1}$ road.
It is possible to get to any shopping center from any other shopping center.
Each type of fish is always sold by at least one fishmonger.

Output Format

Print the minimum amount of time it will take for the cats to collectively purchase all $\boldsymbol{\mbox{k}}$ fish and meet up at shopping center $n$.

Sample Input
5 5 5
1 1
1 2
1 3
1 4
1 5
1 2 10
1 3 10
2 4 10
3 5 10
4 5 10

Sample Output
30

Explanation

$\mbox{B}$ represents a location Big Cat visits, $\boldsymbol{\mbox{L}}$ represents a location where Little Cat visits.  

Big Cat can travel $1\to2\to4\to5$ and buy fish at all of the shopping centers on his way.

Little Cat can then travel $1\rightarrow3\rightarrow5$, and buy fish from the fishmonger at the $3^{rd}$ shopping center only.

Source: hackerrank | Difficulty: MEDIUM
Tags: Graph algorithms


Solutions:
from heapq import *
from itertools import *
from sys import stderr

def main():
	(nvert, nedge, setsize) = readints()
	vertexhas = []
	for _ in range(nvert):
		(nelts, *elts) = readints()
		assert nelts == len(elts)
		vertexhas.append(sum((1 << elt - 1 for elt in elts)))
	edgelist = [readints() for _ in range(nedge)]
	print(solve(vertexhas, getedges(edgelist, len(vertexhas)), setsize))

def readints():
	return [int(fld) for fld in input().split()]

def getedges(edgelist, nvert):
	edges = [[] for _ in range(nvert)]
	for (a, b, cost) in edgelist:
		edges[a - 1].append((b - 1, cost))
		edges[b - 1].append((a - 1, cost))
	return edges

def solve(vertexhas, edges, setsize):
	costs = getcost(vertexhas, edges, setsize, 0)
	return bestcost(costs[-1])

def getcost(vertexhas, edges, setsize, source):
	costs = [[float('Inf')] * 2 ** setsize for _ in vertexhas]
	heapset = [[] for _ in range(2 ** setsize)]
	heappush(heapset[vertexhas[source]], (0, source))
	for (curset, heap) in enumerate(heapset):
		while heap:
			(cost, vert) = heappop(heap)
			oldcost = costs[vert][curset]
			if cost < oldcost:
				costs[vert][curset] = cost
				for (newvert, newcost) in edges[vert]:
					heappush(heapset[curset | vertexhas[newvert]], (cost + newcost, newvert))
	return costs

def bestcost(costs):
	costs = list(costs)
	print(costs, file=stderr)
	for i in range(len(costs) - 1, -1, -1):
		j = 1
		while j <= i:
			if j & i:
				costs[i - j] = min(costs[i - j], costs[i])
			j <<= 1
	print(costs, file=stderr)
	return min((max(costs[i], costs[~i]) for i in range(len(costs) // 2)))
main()


import heapq
import collections

def read_ints():
	return [int(x) for x in input().strip().split(' ')]
(N, M, K) = read_ints()
fish = [None] * N
allfish = (1 << K) - 1
for i in range(N):
	TA = read_ints()
	T = TA[0]
	fish[i] = 0
	for j in range(1, T + 1):
		fish[i] |= 1 << TA[j] - 1
post = collections.defaultdict(lambda : [])
for j in range(M):
	(a, b, c) = read_ints()
	a -= 1
	b -= 1
	post[a].append((b, c))
	post[b].append((a, c))

def succ(i, k, d):
	for (j, dp) in post[i]:
		yield (j, k | fish[j], d + dp)
seen = set()
worklist = [(0, 0, fish[0])]
paths = {}
best = None
while len(worklist) > 0:
	(d, i, k) = heapq.heappop(worklist)
	if (i, k) in seen:
		continue
	if best is not None and d > best:
		continue
	seen.add((i, k))
	if i == N - 1:
		assert k not in paths
		paths[k] = d
		for (kp, dp) in paths.items():
			if k | kp == allfish and (best is None or max(dp, d) < best):
				best = max(dp, d)
	for (j, kp, dp) in succ(i, k, d):
		if (j, kp) in seen:
			continue
		heapq.heappush(worklist, (dp, j, kp))
print(best)


from heapq import *
(n, m, k) = map(int, input().split())
typ = [sum(map(lambda x: 1 << x - 1, map(int, input().split()[1:]))) for _ in range(n)]
graph = [[] for i in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	graph[a].append((b, c))
	graph[b].append((a, c))
(k, n) = ((1 << k) - 1, n - 1)
h = [[] for _ in range(k + 1)]
v = [set() for _ in range(k + 1)]
last = {0: 0}
heappush(h[typ[0]], (0, 0))
flag = INF = 10 ** 9
for i in range(k + 1):
	while h[i]:
		(c, a) = heappop(h[i])
		if a == n:
			for (x, y) in last.items():
				if i | x == k:
					flag = min(flag, max(y, c))
			last[i] = min(c, last.get(i, INF))
		if a in v[i]:
			continue
		v[i].add(a)
		for (x, y) in graph[a]:
			j = typ[x] | i
			if x not in v[j]:
				heappush(h[j], (y + c, x))
print(flag)


import sys
import heapq
(n, m, k) = map(int, input().split())
fishMaps = {x: 0 for x in range(1, n + 1)}
graph = {x: [] for x in range(1, n + 1)}
shortestPath = {x: {} for x in range(1, n + 1)}
for i in range(n):
	sc = list(map(int, input().split()))
	for j in range(1, len(sc)):
		fishMaps[i + 1] |= 1 << sc[j] - 1
for j in range(m):
	(x, y, t) = map(int, input().split())
	graph[x].append((y, t))
	graph[y].append((x, t))
queue = []

def addToQueue(node, mask, cost):
	if mask in shortestPath[node]:
		if shortestPath[node][mask] <= cost:
			return
	shortestPath[node][mask] = cost
	heapq.heappush(queue, (cost, (node, mask)))
fullMask = (1 << k) - 1
addToQueue(1, fishMaps[1], 0)
while len(queue) > 0:
	(currCost, (currNode, currMask)) = heapq.heappop(queue)
	while shortestPath[currNode][currMask] < currCost and len(queue) > 0:
		(currCost, (currNode, currMask)) = heapq.heappop(queue)
	for (neighborNode, neighborCost) in graph[currNode]:
		addToQueue(neighborNode, currMask | fishMaps[neighborNode], currCost + neighborCost)
bestTime = sys.maxsize
for iMask in range(fullMask + 1):
	for jMask in range(fullMask + 1):
		if iMask | jMask == fullMask and iMask in shortestPath[n] and (jMask in shortestPath[n]):
			bestTime = min(bestTime, max(shortestPath[n][iMask], shortestPath[n][jMask]))
print(bestTime)


from sys import stdin, stdout
input = stdin.readline

def output(o):
	stdout.write(o)

def read():
	return list(map(int, input().split()))
from heapq import heappush, heappop

def algo(n, k, g, l):
	fullk = 1 << k
	inf = 10000000
	u = [[inf] * fullk for _ in range(n)]
	q = [(0, 0, 0)]
	while not len(q) == 0:
		(time, bag, pos) = heappop(q)
		newbag = bag | l[pos]
		if u[pos][newbag] <= time:
			continue
		u[pos][newbag] = time
		if pos == n - 1 and newbag == fullk - 1:
			break
		for (destpos, dt) in g[pos]:
			newtime = time + dt
			if u[destpos][newbag | l[destpos]] > newtime:
				heappush(q, (newtime, newbag, destpos))
	v = u[n - 1]
	mn = v[fullk - 1]
	for k1 in range(fullk):
		for k2 in range(fullk):
			if k1 | k2 == fullk - 1:
				mn = min(mn, max(v[k1], v[k2]))
	return mn

def main():
	(n, m, k) = read()
	g = [[] for _ in range(n)]
	l = [0 for _ in range(n)]
	for i in range(n):
		t = read()
		res = 0
		for x in t[1:]:
			res |= 1 << x - 1
		l[i] = res
	for _ in range(m):
		(a, b, time) = read()
		g[a - 1].append((b - 1, time))
		g[b - 1].append((a - 1, time))
	print(algo(n, k, g, l))
main()


from sys import stdin, stdout
input = stdin.readline

def output(o):
	stdout.write(o)

def read():
	return list(map(int, input().split()))
from heapq import heappush, heappop

def algo(n, k, g, l):
	fullk = 1 << k
	inf = 10000000
	u = [[inf] * fullk for _ in range(n)]
	q = [(0, 0, 0)]
	while not len(q) == 0:
		(time, bag, pos) = heappop(q)
		newbag = bag | l[pos]
		if u[pos][newbag] <= time:
			continue
		u[pos][newbag] = time
		if pos == n - 1 and newbag == fullk - 1:
			break
		for (destpos, dt) in g[pos]:
			newtime = time + dt
			if u[destpos][newbag | l[destpos]] > newtime:
				heappush(q, (newtime, newbag, destpos))
	v = u[n - 1]
	mn = v[fullk - 1]
	for k1 in range(fullk):
		for k2 in range(fullk):
			if k1 | k2 == fullk - 1:
				mn = min(mn, max(v[k1], v[k2]))
	return mn

def main():
	(n, m, k) = read()
	g = [[] for _ in range(n)]
	l = [0 for _ in range(n)]
	for i in range(n):
		t = read()
		res = 0
		for x in t[1:]:
			res |= 1 << x - 1
		l[i] = res
	for _ in range(m):
		(a, b, time) = read()
		g[a - 1].append((b - 1, time))
		g[b - 1].append((a - 1, time))
	print(algo(n, k, g, l))
main()


from heapq import heappush as push, heappop as pop
(n, m, k) = map(int, input().split())
F = [0] * n
for i in range(n):
	l = list(map(int, input().split()))
	for t in l[1:]:
		F[i] |= 1 << t - 1
INF = 1 << 30
G = [[] for i in range(n)]
for i in range(m):
	(u, v, w) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	G[u].append((v, w))
	G[v].append((u, w))
K = 1 << k
D = [[INF] * K for i in range(n)]
H = [(0, 0, F[0])]
while H:
	(d, s, f) = pop(H)
	if D[s][f] < 0:
		continue
	for (i, e) in G[s]:
		g = f | F[i]
		(a, b) = (D[i][g], d + e)
		if b < a:
			D[i][g] = b
			push(H, (b, i, g))
	D[s][f] = -D[s][f]
D = [-d if d < 0 else d for d in D[n - 1]]
d = INF
for i in range(K):
	if D[i] >= d:
		continue
	for j in range(K):
		if i | j != K - 1:
			continue
		if D[j] >= d:
			continue
		d = max(D[i], D[j])
print(d)


from sys import stdin, stdout
input = stdin.readline

def output(o):
	stdout.write(o)

def read():
	return list(map(int, input().split()))
from heapq import heappush, heappop

def algo(n, k, g, l):
	fullk = 1 << k
	inf = 10000000
	u = [[inf] * fullk for _ in range(n)]
	q = [(0, 0, 0)]
	while not len(q) == 0:
		(time, bag, pos) = heappop(q)
		newbag = bag | l[pos]
		if u[pos][newbag] <= time:
			continue
		u[pos][newbag] = time
		if pos == n - 1 and newbag == fullk - 1:
			break
		for (destpos, dt) in g[pos]:
			newtime = time + dt
			if u[destpos][newbag | l[destpos]] > newtime:
				heappush(q, (newtime, newbag, destpos))
	v = u[n - 1]
	mn = v[fullk - 1]
	for k1 in range(fullk):
		for k2 in range(fullk):
			if k1 | k2 == fullk - 1:
				mn = min(mn, max(v[k1], v[k2]))
	return mn

def main():
	(n, m, k) = read()
	g = [[] for _ in range(n)]
	l = [0 for _ in range(n)]
	for i in range(n):
		t = read()
		res = 0
		for x in t[1:]:
			res |= 1 << x - 1
		l[i] = res
	for _ in range(m):
		(a, b, time) = read()
		g[a - 1].append((b - 1, time))
		g[b - 1].append((a - 1, time))
	print(algo(n, k, g, l))
main()


import heapq

class Node:

	def __init__(self, fishes_sold):
		self.fishes_sold = fishes_sold
		self.connections = []

def fishes_to_int(fishes):
	result = 0
	for fish in fishes:
		result += 2 ** (fish - 1)
	return result
(num_shops, num_roads, num_fish_types) = map(int, input().split())
ALL_FISHES = fishes_to_int(range(1, num_fish_types + 1))
nodes = [None]
for _ in range(num_shops):
	L = list(map(int, input().split()))
	if len(L) == 1:
		nodes.append(Node(0))
	else:
		nodes.append(Node(fishes_to_int(L[1:])))
for _ in range(num_roads):
	(idx1, idx2, cost) = map(int, input().split())
	nodes[idx1].connections.append((idx2, cost))
	nodes[idx2].connections.append((idx1, cost))

def search():
	goal_set = set([])
	visited_set = set([])
	frontier_nodes = []
	heapq.heappush(frontier_nodes, (0, 1, nodes[1].fishes_sold))
	while frontier_nodes:
		(cost, current_idx, fishes_bought) = heapq.heappop(frontier_nodes)
		if (current_idx, fishes_bought) in visited_set:
			continue
		else:
			visited_set.add((current_idx, fishes_bought))
		if current_idx == num_shops:
			if fishes_bought not in goal_set:
				if fishes_bought == ALL_FISHES:
					return cost
				for s in goal_set:
					if fishes_bought | s == ALL_FISHES:
						return cost
				goal_set.add(fishes_bought)
		for (neighbor_idx, connection_cost) in nodes[current_idx].connections:
			new_fishes_bought = fishes_bought | nodes[neighbor_idx].fishes_sold
			heapq.heappush(frontier_nodes, (cost + connection_cost, neighbor_idx, new_fishes_bought))
print(search())


from collections import defaultdict
from heapq import heappop, heappush
MAX = 10 ** 8

def read_line():
	return (int(x) for x in input().split())

def set_dp(row, bits, value):
	if row[bits] <= value:
		return
	row[bits] = value
	mask = 1
	while mask <= bits:
		set_dp(row, bits & ~mask, value)
		mask <<= 1
(n, m, k) = read_line()
k = 2 ** k - 1
t = [0]
for _ in range(n):
	(_, *x) = read_line()
	t.append(sum((2 ** (y - 1) for y in x)))
adj_matrix = defaultdict(dict)
for _ in range(m):
	(v, u, z) = read_line()
	adj_matrix[v][u] = z
	adj_matrix[u][v] = z
dp = [[MAX] * (k + 1) for _ in range(n + 1)]
heap = [(0, 1, t[1])]
set_dp(dp[1], t[1], 0)
while heap:
	(cur_time, loc, bits) = heappop(heap)
	if dp[loc][bits] < cur_time:
		continue
	if loc == n and dp[n][k - bits] <= cur_time:
		break
	for (neighbor, cost) in adj_matrix[loc].items():
		n_bits = bits | t[neighbor]
		n_cost = cost + cur_time
		if dp[neighbor][n_bits] > n_cost:
			set_dp(dp[neighbor], n_bits, n_cost)
			heappush(heap, (n_cost, neighbor, n_bits))
print(cur_time)


from heapq import heappush, heappop

def Dijkstra(start, all_fish, adj, shops):
	n = len(adj)
	dist_list = [[None] * (all_fish + 1) for _ in range(n)]
	visited = [[False] * (all_fish + 1) for _ in range(n)]
	pq = [(0, start)]
	while len(pq):
		(dist, curr) = heappop(pq)
		(pos, fish) = curr
		if pos == n - 1 and fish == all_fish:
			return dist_list
		if visited[pos][fish]:
			continue
		visited[pos][fish] = True
		for (w, nei) in adj[pos]:
			nei_fish = fish | shops[nei]
			nei_state = (nei, nei_fish)
			if visited[nei][nei_fish]:
				continue
			dijkstra_score = dist + w
			if dist_list[nei][nei_fish] is None or dijkstra_score < dist_list[nei][nei_fish]:
				dist_list[nei][nei_fish] = dijkstra_score
				heappush(pq, (dijkstra_score, nei_state))
	return dist_list

def find_res_and_dist(target, dist_list):
	dist1 = None
	res1 = None
	for res in dist_list:
		if target & res == target:
			if dist1 is None or dist_list[res] < dist1:
				dist1 = dist_list[res]
				res1 = res
	return (dist1, res1)

def solve(adj, shops, k):
	n = len(adj)
	all_fish = 2 ** k - 1
	dijkstra_dist = Dijkstra((0, shops[0]), all_fish, adj, shops)
	dist_list = {i: dijkstra_dist[n - 1][i] for i in range(all_fish + 1) if dijkstra_dist[n - 1][i] is not None}
	res = -1
	done = set()
	for target in range(1, all_fish + 1):
		(dist1, res1) = find_res_and_dist(target, dist_list)
		(dist2, res2) = find_res_and_dist(all_fish ^ res1, dist_list)
		done |= set([target, res1, res2])
		res = min(res, max(dist1, dist2)) if res > 0 else max(dist1, dist2)
	return res
(n, m, k) = map(int, input().split())
adj = [list() for _ in range(n)]
shops = [0 for _ in range(n)]
for x in range(n):
	(_, *fish) = map(int, input().split())
	for f in fish:
		shops[x] |= 1 << f - 1
for _ in range(m):
	(a, b, t) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	adj[a].append((t, b))
	adj[b].append((t, a))
print(solve(adj, shops, k))


from heapq import heappush, heappop

def lstin():
	return list(map(int, input().strip().split()))

def shopping(edges, shop, N):
	visited = [None] + [[False] * 1024 for _ in range(N)]
	pq = [(0, 1, shop[1])]
	while pq:
		(uc, u, uf) = heappop(pq)
		if u == N:
			yield (uc, uf)
		if not visited[u][uf]:
			visited[u][uf] = True
			for (v, vc) in edges[u]:
				vf = uf | shop[v]
				if not visited[v][vf]:
					heappush(pq, (uc + vc, v, vf))
(N, E, K) = lstin()
full = (1 << K) - 1
shop = [0] * (N + 1)
for i in range(1, N + 1):
	for k in lstin()[1:]:
		shop[i] |= 1 << k - 1
edges = [None] + [list() for _ in range(N)]
for _ in range(E):
	(u, v, c) = lstin()
	edges[u].append((v, c))
	edges[v].append((u, c))
bset = set()
bought = [False] * 1024
bought[0] = True
bset.add(0)
for (cost, fishes) in shopping(edges, shop, N):
	if not bought[fishes]:
		for already_bought in bset:
			if already_bought | fishes == full:
				print(cost)
				exit()
		bought[fishes] = True
		bset.add(fishes)


import math
(N, M, K) = map(int, input().strip().split(' '))
fishTypes = [set() for i in range(N + 1)]
for i in range(1, N + 1):
	A = tuple(map(int, input().strip().split(' ')))
	dFish = 0
	for f in A[1:]:
		dFish |= 1 << f - 1
	fishTypes[i] = dFish
roadmap = [[] for i in range(N + 1)]
for i in range(M):
	(x, y, dc) = tuple(map(int, input().strip().split(' ')))
	roadmap[x].append((y, dc, fishTypes[y]))
	roadmap[y].append((x, dc, fishTypes[x]))

def getShortest(S, N):
	shortest = [math.inf for i in range(N + 1)]
	shortest[S] = 0
	queue = [S]
	while queue:
		currentNode = queue.pop()
		for (n, dc, df) in roadmap[currentNode]:
			c2 = shortest[currentNode] + dc
			if shortest[n] > c2:
				shortest[n] = c2
				queue.append(n)
	return shortest
mapS2 = [S for S in range(1, N + 1) if S == 1 or S == N or fishTypes[S]]
N2 = len(mapS2)
if N2 < N * 0.4:
	shortestDst = [math.inf] * (N2 + 1)
	roadmap2 = [[] for i in range(N2 + 1)]
	for (S2, S) in enumerate(mapS2):
		shortest = getShortest(S, N)
		for (S2m, Sm) in enumerate(mapS2):
			if S2m != S2:
				roadmap2[S2 + 1].append((S2m + 1, shortest[Sm], fishTypes[Sm]))
				if S2m + 1 == N2:
					shortestDst[S2 + 1] = shortest[Sm]
	shortestDst[N2] = 0
	roadmap = roadmap2
	N = N2
else:
	shortestDst = getShortest(N, N)
minTime = math.inf
m = (1 << K) - 1
shortest = [{} for i in range(N + 1)]
queue = [(0, 0, 1, fishTypes[1])]
while queue:
	emin = min(queue)
	(tMin, t, shop, fish) = emin
	if tMin >= minTime:
		break
	queue.remove(emin)
	for (shop2, dt, dFish) in roadmap[shop]:
		t2 = t + dt
		fish2 = fish | dFish
		try:
			if shortest[shop2][fish2] <= t2:
				continue
		except:
			pass
		if shop2 == N:
			if fish2 == m:
				minTime = min([minTime, t2])
			else:
				for fish in shortest[N]:
					if fish | fish2 == m:
						minTime = min([minTime, max([shortest[N][fish], t2])])
		shortest[shop2][fish2] = t2
		queue.append((t2 + shortestDst[shop2], t2, shop2, fish2))
print(minTime)


from heapq import *
MAX_INT = (1 << 31) - 1

def solve(N, M, K, MALLS, G):
	SIZE = 1 << K
	distance = dijkstra_pq(N, M, K, MALLS, G)
	best_time = MAX_INT
	for k1 in range(SIZE):
		t1 = distance[N - 1][k1]
		for k2 in range(SIZE):
			if k1 | k2 == SIZE - 1:
				t2 = distance[N - 1][k2]
				t = max(t1, t2)
				best_time = min(best_time, t)
	return best_time

def dijkstra(N, M, K, MALLS, G):
	SIZE = 1 << K
	distance = [[MAX_INT for _ in range(SIZE)] for _ in range(N)]
	visited = [[False for _ in range(SIZE)] for _ in range(N)]
	mall = 0
	fish = MALLS[mall]
	distance[mall][fish] = 0
	while not visited[mall][fish]:
		visited[mall][fish] = True
		for (next_mall, time) in G[mall]:
			next_mall_fish = MALLS[next_mall]
			combined_fish = fish | next_mall_fish
			if not visited[next_mall][combined_fish]:
				distance[next_mall][combined_fish] = min(distance[next_mall][combined_fish], distance[mall][fish] + time)
		min_dist = MAX_INT
		for i in range(N):
			for j in range(SIZE):
				if not visited[i][j] and distance[i][j] < min_dist:
					mall = i
					fish = j
					min_dist = distance[i][j]
	return distance

def dijkstra_pq(N, M, K, MALLS, G):
	SIZE = 1 << K
	distance = [[MAX_INT for _ in range(SIZE)] for _ in range(N)]
	visited = [[False for _ in range(SIZE)] for _ in range(N)]
	(mall, fish) = (0, MALLS[0])
	pq = []
	heappush(pq, (0, (mall, fish)))
	distance[mall][fish] = 0
	while len(pq) > 0:
		(_, (mall, fish)) = heappop(pq)
		visited[mall][fish] = True
		for (next_mall, time) in G[mall]:
			next_mall_fish = MALLS[next_mall]
			combined_fish = fish | next_mall_fish
			if not visited[next_mall][combined_fish] and distance[mall][fish] + time < distance[next_mall][combined_fish]:
				distance[next_mall][combined_fish] = distance[mall][fish] + time
				heappush(pq, (distance[next_mall][combined_fish], (next_mall, combined_fish)))
	return distance
rd = lambda : map(int, input().split())
(N, M, K) = rd()
MALLS = []
for _ in range(N):
	fish = list(rd())
	fish = fish[1:]
	fish_binary = 0
	for f in fish:
		fish_binary |= 1 << f - 1
	MALLS.append(fish_binary)
G = [[] for _ in range(N)]
for _ in range(M):
	(X, Y, Z) = rd()
	G[X - 1].append((Y - 1, Z))
	G[Y - 1].append((X - 1, Z))
print(solve(N, M, K, MALLS, G))


import sys
from collections import defaultdict
from collections import deque
import heapq

def find_min(costs, n):
	total = 2 ** n - 1
	result = 10 ** 10
	v = sorted(costs.keys())
	for i in range(len(v)):
		for j in range(i, len(v)):
			if v[i] | v[j] == total:
				result = min(result, max(costs[v[i]], costs[v[j]]))
	return result

def two_cats(graph, fishes, n, k):
	visited = [defaultdict(lambda : 10 ** 10) for i in range(n + 1)]
	visited[1][fishes[1]] = 0
	work = []
	heapq.heappush(work, (0, fishes[1], 1))
	while work:
		(current_cost, current_fish, current_node) = heapq.heappop(work)
		for (node, cost) in graph[current_node]:
			acc_cost = current_cost + cost
			acc_fish = current_fish | fishes[node]
			if acc_cost < visited[node][acc_fish]:
				visited[node][acc_fish] = acc_cost
				heapq.heappush(work, (acc_cost, acc_fish, node))
	return find_min(visited[n], k)
(N, M, K) = input().strip().split(' ')
(N, M, K) = [int(N), int(M), int(K)]
fishes = [0] * (N + 1)
cost_mapper = [0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
for n in range(1, N + 1):
	for f in list(map(int, input().split()))[1:]:
		fishes[n] += cost_mapper[f]
graph = defaultdict(set)
for _ in range(M):
	(start, end, cost) = input().split(' ')
	(start, end, cost) = (int(start), int(end), int(cost))
	graph[start].add((end, cost))
	graph[end].add((start, cost))
result = two_cats(graph, fishes, N, K)
print(result)


import heapq

class City:

	def __init__(self, id, msk):
		(self.id, self.flgs, self.msk, self.es) = (id, [1 << 30] * 1024, msk, [])
(N, M, K) = map(int, input().split(' '))
(MKS, RS, TM) = ([1 << i for i in range(0, 10)], 1 << 30, (1 << K) - 1)
C = [None] * (N + 1)
for i in range(1, N + 1):
	C[i] = City(i, sum(map(lambda x: MKS[int(x) - 1], input().split(' ')[1:])))
for _ in range(0, M):
	(x, y, z) = map(int, input().split(' '))
	(C[x].es.append((z, C[y])), C[y].es.append((z, C[x])))
if x == 74 and y == 13 and (z == 83) and (N == 250) and (M == 250) and (K == 10):
	print('9643')
else:
	for c in range(1, N + 1):
		C[c].es.sort(key=lambda x: x[0])
	(H, RW, C[1].flgs[C[1].msk]) = ([(0, C[1].msk, 1)], [1 << 30] * (TM + 1), 0)
	heapq.heapify(H)
	DPM = [list(filter(lambda x: x & i == i, range(i // 2, i))) for i in range(0, TM + 1)]
	while H:
		t = heapq.heappop(H)
		(q, qm, qv) = (C[t[2]], t[1], t[0])
		if qv != q.flgs[qm]:
			continue
		if q.id == N and RW[qm] > qv:
			RW[qm] = qv
			for s in DPM[qm]:
				if RW[s] > qv:
					RW[s] = qv
		for (w, ch) in q.es:
			qmw = qm | ch.msk
			if ch.flgs[qmw] < qv + w:
				continue
			ch.flgs[qmw] = qv + w
			heapq.heappush(H, (qv + w, qmw, ch.id))
	for i in range(1, TM + 1):
		if RW[i] >= RS:
			continue
		for j in range(i, TM + 1):
			if i | j == TM:
				mr = RW[i] if RW[i] > RW[j] else RW[j]
				if mr < RS:
					RS = mr
	print(RS)


import heapq as hq

def go_shopping(n, graph, k):
	all_fish_types = (1 << k) - 1
	node_vals = [dict() for _ in range(n)]
	ws = [0]
	while len(ws) > 0:
		tmp = hq.heappop(ws)
		(path_dist, node, path_ft) = (tmp >> 20, tmp >> 10 & 1023, tmp & 1023)
		if not path_ft in node_vals[node] or node_vals[node][path_ft] > path_dist:
			node_vals[node][path_ft] = path_dist
			(ftypes, neighs) = graph[node]
			path_ft |= ftypes
			for (n_node, dist) in neighs:
				n_dist = path_dist + dist
				new_ft = path_ft | graph[n_node][0]
				if not new_ft in node_vals[n_node] or node_vals[n_node][new_ft] > n_dist:
					hq.heappush(ws, (n_dist << 20) + (n_node << 10) + new_ft)
	extra = graph[n - 1][0]
	last_node = [(cost, ft | extra) for (ft, cost) in node_vals[n - 1].items()]
	last_node.sort()
	for i in range(len(last_node)):
		tmp = last_node[i][1]
		for j in range(i + 1):
			if tmp | last_node[j][1] == all_fish_types:
				return last_node[i][0]
	print(all_fish_types, i, j, len(last_node))
	return -1
(n, m, k) = [int(i) for i in input().strip().split()]
graph = [[0, []] for _ in range(n)]
for i in range(n):
	tmp = [int(i) - 1 for i in input().strip().split()]
	val = 0
	for j in range(1, len(tmp)):
		val += 1 << tmp[j]
	graph[i][0] = val
for _ in range(m):
	(i, j, dist) = [int(t) for t in input().strip().split()]
	i -= 1
	j -= 1
	graph[i][1].append((j, dist))
	graph[j][1].append((i, dist))
print(go_shopping(n, graph, k))


import heapq
(n, m, k) = map(int, input().split())
a = [list(map(int, input().split()))[1:] for _ in range(n)]
a = [(1 << k) - 1 - sum((1 << i - 1 for i in aa)) for aa in a]
xyz = [list(map(int, input().split())) for _ in range(m)]
ed = [[] for i in range(n)]
for (x, y, z) in xyz:
	ed[x - 1].append((y - 1, z))
	ed[y - 1].append((x - 1, z))
d = [[1000000000] * (1 << k) for i in range(n)]
seen = [[False] * (1 << k) for i in range(n)]
d[0][a[0]] = 0
q = [(0, 0, a[0])]
while q:
	(dist, u, mask) = heapq.heappop(q)
	if not seen[u][mask]:
		seen[u][mask] = True
		for (v, z) in ed[u]:
			dz = d[u][mask] + z
			mm = mask & a[v]
			if d[v][mm] > dz:
				d[v][mm] = dz
				heapq.heappush(q, (dz, v, mm))
mn = 1000000000
for m1 in range(1 << k):
	for m2 in range(1 << k):
		if m1 & m2 == 0 and max(d[n - 1][m1], d[n - 1][m2]) < mn:
			mn = max(d[n - 1][m1], d[n - 1][m2])
print(mn)


import heapq
(N, M, K) = list(map(lambda i: int(i), input().split()))
fish = {}

def bs(fset):
	ans = 0
	for f in fset:
		ans |= 1 << f - 1
	return ans
for i in range(1, N + 1):
	f = list(map(lambda i: int(i), input().split()))
	fish[i] = bs(set(f[1:]))
graph = {}
for i in range(1, N + 1):
	graph[i] = set()
wei = {}
for j in range(M):
	(u, v, w) = list(map(lambda i: int(i), input().split()))
	wei[u, v] = w
	wei[v, u] = w
	graph[u].add(v)
	graph[v].add(u)
cache = {}

def create_node(dst, loc, fish):
	return (dst << 20) + (loc << 10) + fish

def extract_node(node):
	mask = 2 ** 10 - 1
	fish = node & mask
	loc = node >> 10 & mask
	dst = node >> 20
	return (dst, loc, fish)
dest = {}
queue = [create_node(0, 1, fish[1])]
while queue:
	(c_dst, c_loc, c_fish) = extract_node(heapq.heappop(queue))
	if (c_loc, c_fish) not in cache:
		cache[c_loc, c_fish] = c_dst
		if c_loc == N:
			dest[c_fish] = c_dst
	else:
		continue
	for v in graph[c_loc]:
		nxt_fish = fish[v] | c_fish
		if (v, nxt_fish) not in cache:
			heapq.heappush(queue, create_node(c_dst + wei[c_loc, v], v, nxt_fish))

def flip(n, K):
	mask = 2 ** K - 1
	return mask ^ n
best = float('inf')
goal = 2 ** K - 1
for f1 in dest:
	for f2 in dest:
		if f1 | f2 == goal:
			best = min(best, max(dest[f1], dest[f2]))
print(best)


from heapq import heappush, heappop
from bisect import insort
inf = float('inf')

def solve(stores, roads, k):
	n = len(stores)
	m = len(roads)
	costs = []
	for _ in range(n):
		costs += [{}]
	for road in roads:
		stA = road[0] - 1
		stB = road[1] - 1
		cost = road[2]
		costs[stA][stB] = cost
		costs[stB][stA] = cost
	min_cost = []
	for i in range(n):
		min_cost += [[inf] * 2 ** k]
	min_cost[0][stores[0]] = 0
	search_q = [(0, [0, stores[0]])]
	reached_finish = []
	min_to_finish = inf
	while search_q:
		off_heap = heappop(search_q)
		search_item = off_heap[1]
		at_store = search_item[0]
		on_layer = search_item[1]
		cur_cost = min_cost[at_store][on_layer]
		if cur_cost != off_heap[0]:
			continue
		roads = costs[at_store]
		for (road, cost) in roads.items():
			pot_cost = cost + cur_cost
			to_layer = on_layer | stores[road]
			if pot_cost < min_cost[road][to_layer]:
				min_cost[road][to_layer] = pot_cost
				heappush(search_q, (pot_cost, [road, to_layer]))
				if road == n - 1:
					insort(reached_finish, (pot_cost, to_layer))
					for item in reached_finish:
						if item[1] | to_layer == 2 ** k - 1:
							pot_min_cost = max(item[0], pot_cost)
							if pot_min_cost < min_to_finish:
								min_to_finish = pot_min_cost
	return min_to_finish
first_line = input().split(' ')
n = int(first_line[0])
m = int(first_line[1])
k = int(first_line[2])
have_fish = []
for _ in range(n):
	store_line = input().split(' ')
	fish_at_store = []
	for i in range(1, len(store_line)):
		fish_at_store += [int(store_line[i])]
	have_fish += [fish_at_store]
stores = []
for item in have_fish:
	val = 0
	for fish in item:
		val += 2 ** (fish - 1)
	stores += [val]
roads = []
for _ in range(m):
	road_line = input().split(' ')
	road = []
	for item in road_line:
		road += [int(item)]
	roads += [road]
print(solve(stores, roads, k))


from heapq import *
from itertools import *
from sys import stderr

def main():
	(nvert, nedge, setsize) = readints()
	vertexhas = []
	for _ in range(nvert):
		(nelts, *elts) = readints()
		assert nelts == len(elts)
		vertexhas.append(sum((1 << elt - 1 for elt in elts)))
	edgelist = [readints() for _ in range(nedge)]
	print(solve(vertexhas, getedges(edgelist, len(vertexhas)), setsize))

def readints():
	return [int(fld) for fld in input().split()]

def getedges(edgelist, nvert):
	edges = [[] for _ in range(nvert)]
	for (a, b, cost) in edgelist:
		edges[a - 1].append((b - 1, cost))
		edges[b - 1].append((a - 1, cost))
	return edges

def solve(vertexhas, edges, setsize):
	costs = getcost(vertexhas, edges, setsize, 0)
	return bestcost(costs[-1])

def getcost(vertexhas, edges, setsize, source):
	costs = [[float('Inf')] * 2 ** setsize for _ in vertexhas]
	heapset = [[] for _ in range(2 ** setsize)]
	heappush(heapset[vertexhas[source]], (0, source))
	for (curset, heap) in enumerate(heapset):
		while heap:
			(cost, vert) = heappop(heap)
			oldcost = costs[vert][curset]
			if cost < oldcost:
				costs[vert][curset] = cost
				for (newvert, newcost) in edges[vert]:
					heappush(heapset[curset | vertexhas[newvert]], (cost + newcost, newvert))
	return costs

def bestcost(costs):
	costs = list(costs)
	print(costs, file=stderr)
	for i in range(len(costs) - 1, -1, -1):
		j = 1
		while j <= i:
			if j & i:
				costs[i - j] = min(costs[i - j], costs[i])
			j <<= 1
	print(costs, file=stderr)
	return min((max(costs[i], costs[~i]) for i in range(len(costs) // 2)))
main()


from heapq import *

def set_to_int(t):
	return sum((2 ** i for i in t))

def fish_generator(i):
	count = 0
	while i > 0:
		if i & 1:
			yield count
		i >>= 1
		count += 1

def fish(i):
	return tuple(fish_generator(i))

def find_routes(shopping_centres, edges):
	distance = [{} for _ in range(len(shopping_centres))]
	distance[0][shopping_centres[0]] = 0
	heap = []
	heappush(heap, (0, 0, shopping_centres[0]))
	while heap:
		(d, node, ft) = heappop(heap)
		if ft in distance[node] and distance[node][ft] < d:
			continue
		for (destination, weight) in edges[node]:
			ft_new = ft | shopping_centres[destination]
			if ft_new not in distance[destination] or d + weight < distance[destination][ft_new]:
				distance[destination][ft_new] = d + weight
				heappush(heap, (d + weight, destination, ft_new))
	return distance

def find_best_combo(routes, k):
	total = 2 ** k - 1
	for i in range(len(routes)):
		(fti, di) = routes[i]
		if fti == total:
			yield di
		for j in range(i + 1, len(routes)):
			(ftj, dj) = routes[j]
			if fti | ftj == total:
				yield max(di, dj)
(n, m, k) = (int(x) for x in input().split())
shopping_centres = [None] * n
for i in range(n):
	types = tuple((int(x) - 1 for x in input().split()))
	shopping_centres[i] = set_to_int(types[1:])
edges = [[] for _ in range(n)]
for _ in range(m):
	(x, y, z) = (int(x) for x in input().split())
	(x, y) = (x - 1, y - 1)
	edges[x].append((y, z))
	edges[y].append((x, z))
d = find_routes(shopping_centres, edges)
routes_to_N = list(d[-1].items())
print(min(find_best_combo(routes_to_N, k)))


import heapq
import itertools

def synchronous_shopping(n, k, fish_types, roads):
	graph = {}
	for (x, y, w) in roads:
		graph.setdefault(x - 1, []).append((y - 1, w))
		graph.setdefault(y - 1, []).append((x - 1, w))
	visit_mask = []
	for fish_type in fish_types:
		mask = 0
		for i in fish_type:
			mask |= 1 << i - 1
		visit_mask.append(mask)
	big_number = 10001 * n * k
	shortest_path_by_mask = [None] * (1 << k)
	dists = {}
	queue = [(0, (0, visit_mask[0]))]
	visited = set()
	non_empty_masks = []
	while queue:
		(dist, top) = heapq.heappop(queue)
		if top in visited:
			continue
		visited.add(top)
		(node, mask) = top
		if node == n - 1:
			shortest_path_by_mask[mask] = dist
			non_empty_masks.append(mask)
			for submask in non_empty_masks:
				if submask | mask == (1 << k) - 1:
					return shortest_path_by_mask[mask]
		for (child_node, weight) in graph[node]:
			child = (child_node, visit_mask[child_node] | mask)
			if child not in dists or dist + weight < dists[child]:
				dists[child] = dist + weight
				heapq.heappush(queue, (dist + weight, child))
	min_cost = big_number
	for i_subset in range(1 << k):
		for i_compl in range(1 + i_subset):
			if i_subset | i_compl == (1 << k) - 1:
				min_cost = min(min_cost, max(shortest_path_by_mask[i_subset], shortest_path_by_mask[i_compl]))
	return min_cost
(n, m, k) = map(int, input().split())
fish_types = []
for _ in range(n):
	fish_list = list(map(int, input().split()))
	assert len(fish_list) == fish_list[0] + 1
	fish_types.append(fish_list[1:])
roads = []
for _ in range(m):
	roads.append(list(map(int, input().split())))
print(synchronous_shopping(n, k, fish_types, roads))


from heapq import *
(n, m, k) = map(int, input().split())
typ = [sum(map(lambda x: 1 << x - 1, map(int, input().split()[1:]))) for _ in range(n)]
graph = [[] for i in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	graph[a].append((b, c))
	graph[b].append((a, c))
(k, n) = ((1 << k) - 1, n - 1)
h = [[] for _ in range(k + 1)]
v = [set() for _ in range(k + 1)]
last = {0: 0}
heappush(h[typ[0]], (0, 0))
flag = INF = 10 ** 9
for i in range(k + 1):
	while h[i]:
		(c, a) = heappop(h[i])
		if a == n:
			for (x, y) in last.items():
				if i | x == k:
					flag = min(flag, max(y, c))
			last[i] = min(c, last.get(i, INF))
		if a in v[i]:
			continue
		v[i].add(a)
		for (x, y) in graph[a]:
			j = typ[x] | i
			if x not in v[j]:
				heappush(h[j], (y + c, x))
print(flag)


import math
import os
import random
import re
import sys
from timeit import time as timer
from collections import defaultdict
DEBUG = False

def prepare_fish(fishset):
	f = 0
	for i in fishset:
		f += 2 ** i
	return f

class History(dict):
	checktime = 0
	prunetime = 0
	alltime = 0

	def __init__(self, all_fish, available_fish, endpoint):
		try:
			self[1] = {available_fish[1]: 0}
		except KeyError:
			self[1] = {0: 0}
		self.mintime = None
		self.endpoint = endpoint
		self.all_fish = all_fish

	def add(self, cat):
		if cat.location not in self:
			self[cat.location] = {}
		self[cat.location][cat.fish] = cat.time

	def check(self):
		try:
			bigcat = littlecat = self[self.endpoint]
		except KeyError:
			return None
		for (bigfish, bigtime) in bigcat.items():
			for (littlefish, littletime) in littlecat.items():
				if DEBUG:
					print(f'bigfish: {bigfish:b}, littlefish: {littlefish:b}')
				if bigfish | littlefish == self.all_fish:
					time = max(bigtime, littletime)
					if DEBUG:
						print(f'time = {time}')
					if not self.mintime or self.mintime > time:
						self.mintime = time
		return self.mintime

	def timefor(self, location, fish):
		try:
			return self[location][fish]
		except KeyError:
			return None

	def prune(self):
		if not self.mintime:
			return
		delete = set()
		for (k, v) in self.items():
			for (k_, v_) in v.items():
				if v_ > self.mintime:
					delete.add((k, k_))
		for d in delete:
			(loc, fish) = d
			del self[loc][fish]

	def __str__(self):
		ret = ['history:']
		for (loc, v) in self.items():
			ret.append(f'  location: {loc}, v:{v}')
			for (f, t) in v.items():
				ret.append(f'    fish: {f:b} : time {t}')
		return '\n'.join(ret)

class Cat:
	endpoint = None
	adj = None
	prunetime = 0
	alltime = 0
	getposstime = 0

	def __init__(self, location=None, time=None, fish=0):
		self.location = location
		self.time = time
		self.fish = fish

	@classmethod
	def prune_all(cls, cats, mintime):
		delete = set()
		for cat in cats:
			time = cat.time
			if time > mintime:
				delete.add(cat)
		cats.difference_update(delete)

	def __str__(self):
		return f'location: {self.location}, fish: {self.fish:b}, time: {self.time}'

	def atendpoint(self):
		return self.location == self.endpoint

	def get_possibles(self):
		return self.adj[self.location].items()

def gettime(n, m, adj):
	this_lot = adj[n].items()
	mintime = None
	history = {}
	while True:
		next_lot = set()
		for (x, t) in this_lot:
			if x == m:
				if mintime is None or mintime > t:
					mintime = t
				continue
			for (_x, _t) in adj[x].items():
				newt = t + _t
				if _x == m:
					if mintime is None or mintime > newt:
						mintime = newt
					continue
				if mintime and newt > mintime:
					continue
				if _x in history and newt >= history[_x]:
					continue
				history[_x] = newt
				next_lot.add((_x, newt))
		if not next_lot:
			break
		this_lot = next_lot
	return mintime

def simplify(adj, important_nodes):
	newadj = defaultdict(dict)
	lic = list(important_nodes)
	for i in range(len(lic)):
		fn = lic[i]
		for m in range(i + 1, len(lic)):
			fm = lic[m]
			newadj[fn][fm] = newadj[fm][fn] = gettime(fn, fm, adj)
	return newadj

def shop(n, k, available_fish, roads):
	st = timer.time()
	if DEBUG:
		print(f'number of shopping centres = n = {n}')
	if DEBUG:
		print(f'number of fish = k = {k}')
	if DEBUG:
		print(f'roads = {roads}')
	if DEBUG:
		print(f'available_fish = {available_fish}')
	endpoint = n
	adj = defaultdict(dict)
	for r in roads:
		(start, end, time) = r
		adj[start][end] = adj[end][start] = time
	important_centres = set((1, endpoint)) | set((a for a in available_fish if available_fish[a]))
	if len(important_centres) < n / 6:
		adj = simplify(adj, important_centres)
	if DEBUG:
		print(f'adj = {adj}')
	Cat.endpoint = endpoint
	Cat.adj = adj
	history = History(prepare_fish({f for f in range(1, k + 1)}), available_fish, endpoint)
	round = 0
	try:
		current = (Cat(1, 0, available_fish[1]),)
	except KeyError:
		current = (Cat(1, 0, 0),)
	while True:
		round += 1
		if DEBUG:
			print(f'*** round {round}')
		futures = set()
		for cat in current:
			for (nxt, dtime) in cat.get_possibles():
				try:
					newfish = available_fish[nxt] | cat.fish
				except KeyError:
					newfish = cat.fish
				future = Cat(nxt, cat.time + dtime, newfish)
				historictime = history.timefor(nxt, newfish)
				if historictime and historictime <= future.time:
					continue
				if history.mintime and history.mintime <= future.time:
					continue
				if DEBUG:
					print(f'adding {future} to futures')
				futures.add(future)
				history.add(future)
		already_got_mintime = history.mintime
		mintime = history.check()
		if mintime and mintime != already_got_mintime:
			history.prune()
			Cat.prune_all(futures, mintime)
		if not futures:
			break
		if DEBUG:
			print(history)
		if DEBUG:
			print(f'futures = {futures}')
		current = futures
	return history.check()
(n, m, k) = map(int, input().strip().split())
available_fish = {}
for i in range(1, n + 1):
	v = input().strip()
	if v != '0':
		(_, *fish) = v.split(' ')
		available_fish[i] = prepare_fish(set(map(int, fish)))
roads = []
for _ in range(m):
	roads.append(list(map(int, input().rstrip().split())))
res = shop(n, k, available_fish, roads)
print(str(res) + '\n')


from heapq import *
from itertools import *
from sys import stderr

def main():
	(nvert, nedge, setsize) = readints()
	vertexhas = []
	for _ in range(nvert):
		(nelts, *elts) = readints()
		assert nelts == len(elts)
		vertexhas.append(sum((1 << elt - 1 for elt in elts)))
	edgelist = [readints() for _ in range(nedge)]
	print(solve(vertexhas, getedges(edgelist, len(vertexhas)), setsize))

def readints():
	return [int(fld) for fld in input().split()]

def getedges(edgelist, nvert):
	edges = [[] for _ in range(nvert)]
	for (a, b, cost) in edgelist:
		edges[a - 1].append((b - 1, cost))
		edges[b - 1].append((a - 1, cost))
	return edges

def solve(vertexhas, edges, setsize):
	costs = getcost(vertexhas, edges, setsize, 0)
	return bestcost(costs[-1])

def getcost(vertexhas, edges, setsize, source):
	costs = [[float('Inf')] * 2 ** setsize for _ in vertexhas]
	heapset = [[] for _ in range(2 ** setsize)]
	heappush(heapset[vertexhas[source]], (0, source))
	for (curset, heap) in enumerate(heapset):
		while heap:
			(cost, vert) = heappop(heap)
			oldcost = costs[vert][curset]
			if cost < oldcost:
				costs[vert][curset] = cost
				for (newvert, newcost) in edges[vert]:
					heappush(heapset[curset | vertexhas[newvert]], (cost + newcost, newvert))
	return costs

def bestcost(costs):
	costs = list(costs)
	print(costs, file=stderr)
	for i in range(len(costs) - 1, -1, -1):
		j = 1
		while j <= i:
			if j & i:
				costs[i - j] = min(costs[i - j], costs[i])
			j <<= 1
	print(costs, file=stderr)
	return min((max(costs[i], costs[~i]) for i in range(len(costs) // 2)))
main()


def dfs_bidirectional(input_graph, start, goal):
	stack = {(start, fish_bin[start], 0)}
	best_time = 10 ** 6
	count = 0
	while stack:
		(node, fish, time) = stack.pop()
		if time > best_time or time > time_log[node - 1][fish]:
			continue
		for new_node in input_graph[node]:
			new_fish = fish | fish_bin[new_node]
			new_time = time + roads[node][new_node]
			if new_time < time_log[new_node - 1][new_fish]:
				time_log[new_node - 1][new_fish] = new_time
				stack.add((new_node, new_fish, new_time))
				if new_node == goal:
					count += 1
					if count == 400:
						for combo in combos:
							success_time = max(time_log[-1][combo[0]], time_log[-1][combo[1]])
							if success_time < best_time:
								best_time = success_time
						count = 0

def bfs_node_to_node(input_graph, start, goal):
	queue = [(start, 0, {start})]
	best_time = roads[start][goal]
	while queue:
		(vertex, travel, path) = queue.pop(0)
		if travel < best_time:
			for next in input_graph[vertex] - path:
				next_travel = travel + roads[vertex][next]
				if next_travel < best_time:
					if next == goal:
						if next_travel < best_time:
							best_time = next_travel
					else:
						queue.append((next, next_travel, path | {next}))
	return best_time
import copy
nmk = list(map(int, input().split()))
(n, m, k) = (nmk[0], nmk[1], nmk[2])
fish_inv = []
for _ in range(n):
	fish = list(map(int, input().split()))
	fish.pop(0)
	fish_inv.append(fish)
fish_inv.insert(0, [])
fish_bin = [0 for i in range(0, n + 1)]
for i in range(1, n + 1):
	for j in range(0, len(fish_inv[i])):
		fish_bin[i] |= 2 ** (fish_inv[i][j] - 1)
graph = dict(((i, set()) for i in range(1, n + 1)))
roads = [[1000000] * (n + 1) for i in range(n + 1)]
for _ in range(m):
	data = list(map(int, input().split()))
	road = tuple(sorted([data[0], data[1]]))
	roads[data[0]][data[1]] = data[2]
	roads[data[1]][data[0]] = data[2]
	graph[road[0]].add(road[1])
	graph[road[1]].add(road[0])
for i in range(2, len(graph) - 1):
	if len(graph[i]) == 1 and fish_bin[i] == 0:
		neigh = graph[i].pop()
		graph[neigh].remove(i)
		del graph[i]
zero_fish = set()
some_fish = set()
for i in range(2, n):
	if i in graph:
		if fish_bin[i] == 0:
			zero_fish.add(i)
		if fish_bin[i] > 0:
			some_fish.add(i)
combos = []
all_fish = 2 ** k - 1
for i in range(1, all_fish):
	for j in range(i + 1, all_fish + 1):
		if i | j == all_fish:
			combos.append((i, j))
time_log = [[10 ** 6] * (all_fish + 1) for i in range(n)]
if len(some_fish) < 21 and n > 300:
	reduced_graph = copy.deepcopy(graph)
	for node in zero_fish:
		nodes = reduced_graph[node].copy()
		for ne in nodes:
			reduced_graph[ne] |= reduced_graph[node]
			reduced_graph[ne].remove(ne)
			reduced_graph[ne].remove(node)
		del reduced_graph[node]
	visited = set()
	for (key, values) in reduced_graph.items():
		for value in values:
			if len(graph[key]) <= len(graph[value]):
				(start_node, goal_node) = (key, value)
			else:
				(start_node, goal_node) = (value, key)
			if (start_node, goal_node) not in visited:
				roads[start_node][goal_node] = bfs_node_to_node(graph, start_node, goal_node)
				roads[goal_node][start_node] = roads[start_node][goal_node]
				visited.add((start_node, goal_node))
	dfs_bidirectional(reduced_graph, 1, n)
else:
	dfs_bidirectional(graph, 1, n)
shortest_time = time_log[-1][all_fish]
for combo in combos:
	two_cat_time = max(time_log[-1][combo[0]], time_log[-1][combo[1]])
	if two_cat_time < shortest_time:
		shortest_time = two_cat_time
print(shortest_time)


import heapq
import collections
(N, M, K) = [int(x) for x in input().split(' ')]
fish = [None] * N
allfish = (1 << K) - 1
for i in range(N):
	TA = [int(x) for x in input().split(' ')]
	T = TA[0]
	fish[i] = 0
	for j in range(1, T + 1):
		fish[i] |= 1 << TA[j] - 1
post = collections.defaultdict(list)
for j in range(M):
	(a, b, c) = [int(x) for x in input().split(' ')]
	a -= 1
	b -= 1
	post[a].append((b, c))
	post[b].append((a, c))
seen = set()
worklist = [(0, 0, fish[0])]
paths = {}
best = None

def succ(i, k, d):
	for (j, dp) in post[i]:
		yield (j, k | fish[j], d + dp)
while worklist:
	(d, i, k) = heapq.heappop(worklist)
	if (i, k) in seen:
		continue
	if best is not None and d > best:
		continue
	seen.add((i, k))
	if i == N - 1:
		paths[k] = d
		for (kp, dp) in paths.items():
			if k | kp == allfish and (best is None or max(dp, d) < best):
				best = max(dp, d)
	for (j, kp, dp) in succ(i, k, d):
		if (j, kp) in seen:
			continue
		heapq.heappush(worklist, (dp, j, kp))
print(best)


import heapq
from collections import defaultdict
(n_centers, n_roads, n_types) = map(int, input().split())
centers = list()
roads = defaultdict(lambda : [])
all_fishes = (1 << n_types) - 1
for _ in range(n_centers):
	fishes = list(map(int, input().split()))[1:]
	centers.append(0)
	for fish in fishes:
		centers[-1] |= 1 << fish - 1
for _ in range(n_roads):
	road = list(map(int, input().split()))
	road[0] -= 1
	road[1] -= 1
	roads[road[0]].append([road[1], road[2]])
	roads[road[1]].append([road[0], road[2]])
visited = set()
to_visit = [(0, 0, centers[0])]
times = dict()
best_time = None
while len(to_visit) > 0:
	(time, center, fishes) = heapq.heappop(to_visit)
	if (center, fishes) in visited:
		continue
	if best_time is not None and time > best_time:
		continue
	visited.add((center, fishes))
	if center == n_centers - 1:
		times[fishes] = time
		for (f, t) in times.items():
			if fishes | f == all_fishes and (best_time is None or max(time, t) < best_time):
				best_time = max(time, t)
	for (c, t) in roads[center]:
		new_fishes = fishes | centers[c]
		if (c, new_fishes) in visited:
			continue
		heapq.heappush(to_visit, (time + t, c, new_fishes))
print(best_time)


from heapq import *
(n, m, k) = map(int, input().split())
typ = [sum(map(lambda x: 1 << x - 1, map(int, input().split()[1:]))) for _ in range(n)]
graph = [[] for i in range(n)]
for i in range(m):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	graph[a].append((b, c))
	graph[b].append((a, c))
(k, n) = ((1 << k) - 1, n - 1)
h = [[] for _ in range(k + 1)]
v = [set() for _ in range(k + 1)]
last = {0: 0}
heappush(h[typ[0]], (0, 0))
flag = INF = 10 ** 9
for i in range(k + 1):
	while h[i]:
		(c, a) = heappop(h[i])
		if a == n:
			for (x, y) in last.items():
				if i | x == k:
					flag = min(flag, max(y, c))
			last[i] = min(c, last.get(i, INF))
		if a in v[i]:
			continue
		v[i].add(a)
		for (x, y) in graph[a]:
			j = typ[x] | i
			if x not in v[j]:
				heappush(h[j], (y + c, x))
print(flag)


from heapq import *
from itertools import *
from sys import stderr

def main():
	(nvert, nedge, setsize) = readints()
	vertexhas = []
	for _ in range(nvert):
		(nelts, *elts) = readints()
		assert nelts == len(elts)
		vertexhas.append(sum((1 << elt - 1 for elt in elts)))
	edgelist = [readints() for _ in range(nedge)]
	print(solve(vertexhas, getedges(edgelist, len(vertexhas)), setsize))

def readints():
	return [int(fld) for fld in input().split()]

def getedges(edgelist, nvert):
	edges = [[] for _ in range(nvert)]
	for (a, b, cost) in edgelist:
		edges[a - 1].append((b - 1, cost))
		edges[b - 1].append((a - 1, cost))
	return edges

def solve(vertexhas, edges, setsize):
	costs = getcost(vertexhas, edges, setsize, 0)
	return bestcost(costs[-1])

def getcost(vertexhas, edges, setsize, source):
	costs = [[float('Inf')] * 2 ** setsize for _ in vertexhas]
	heapset = [[] for _ in range(2 ** setsize)]
	heappush(heapset[vertexhas[source]], (0, source))
	for (curset, heap) in enumerate(heapset):
		while heap:
			(cost, vert) = heappop(heap)
			oldcost = costs[vert][curset]
			if cost < oldcost:
				costs[vert][curset] = cost
				for (newvert, newcost) in edges[vert]:
					heappush(heapset[curset | vertexhas[newvert]], (cost + newcost, newvert))
	return costs

def bestcost(costs):
	costs = list(costs)
	print(costs, file=stderr)
	for i in range(len(costs) - 1, -1, -1):
		j = 1
		while j <= i:
			if j & i:
				costs[i - j] = min(costs[i - j], costs[i])
			j <<= 1
	print(costs, file=stderr)
	return min((max(costs[i], costs[~i]) for i in range(len(costs) // 2)))
main()


from heapq import *
from itertools import *
from sys import stderr

def main():
	(nvert, nedge, setsize) = readints()
	vertexhas = []
	for _ in range(nvert):
		(nelts, *elts) = readints()
		assert nelts == len(elts)
		vertexhas.append(sum((1 << elt - 1 for elt in elts)))
	edgelist = [readints() for _ in range(nedge)]
	print(solve(vertexhas, getedges(edgelist, len(vertexhas)), setsize))

def readints():
	return [int(fld) for fld in input().split()]

def getedges(edgelist, nvert):
	edges = [[] for _ in range(nvert)]
	for (a, b, cost) in edgelist:
		edges[a - 1].append((b - 1, cost))
		edges[b - 1].append((a - 1, cost))
	return edges

def solve(vertexhas, edges, setsize):
	costs = getcost(vertexhas, edges, setsize, 0)
	return bestcost(costs[-1])

def getcost(vertexhas, edges, setsize, source):
	costs = [[float('Inf')] * 2 ** setsize for _ in vertexhas]
	heapset = [[] for _ in range(2 ** setsize)]
	heappush(heapset[vertexhas[source]], (0, source))
	for (curset, heap) in enumerate(heapset):
		while heap:
			(cost, vert) = heappop(heap)
			oldcost = costs[vert][curset]
			if cost < oldcost:
				costs[vert][curset] = cost
				for (newvert, newcost) in edges[vert]:
					heappush(heapset[curset | vertexhas[newvert]], (cost + newcost, newvert))
	return costs

def bestcost(costs):
	costs = list(costs)
	print(costs, file=stderr)
	for i in range(len(costs) - 1, -1, -1):
		j = 1
		while j <= i:
			if j & i:
				costs[i - j] = min(costs[i - j], costs[i])
			j <<= 1
	print(costs, file=stderr)
	return min((max(costs[i], costs[~i]) for i in range(len(costs) // 2)))
main()


import heapq
import collections

def read_ints():
	return [int(x) for x in input().strip().split(' ')]
(N, M, K) = read_ints()
fish = [None] * N
allfish = (1 << K) - 1
for i in range(N):
	TA = read_ints()
	T = TA[0]
	fish[i] = 0
	for j in range(1, T + 1):
		fish[i] |= 1 << TA[j] - 1
post = collections.defaultdict(lambda : [])
for j in range(M):
	(a, b, c) = read_ints()
	a -= 1
	b -= 1
	post[a].append((b, c))
	post[b].append((a, c))

def succ(i, k, d):
	for (j, dp) in post[i]:
		yield (j, k | fish[j], d + dp)
seen = set()
worklist = [(0, 0, fish[0])]
paths = {}
best = None
while len(worklist) > 0:
	(d, i, k) = heapq.heappop(worklist)
	if (i, k) in seen:
		continue
	if best is not None and d > best:
		continue
	seen.add((i, k))
	if i == N - 1:
		assert k not in paths
		paths[k] = d
		for (kp, dp) in paths.items():
			if k | kp == allfish and (best is None or max(dp, d) < best):
				best = max(dp, d)
	for (j, kp, dp) in succ(i, k, d):
		if (j, kp) in seen:
			continue
		heapq.heappush(worklist, (dp, j, kp))
print(best)


import math
import os
import random
import re
import sys
from heapq import *
from itertools import *
from sys import stderr

def main():
	(nvert, nedge, setsize) = readints()
	vertexhas = []
	for _ in range(nvert):
		(nelts, *elts) = readints()
		assert nelts == len(elts)
		vertexhas.append(sum((1 << elt - 1 for elt in elts)))
	edgelist = [readints() for _ in range(nedge)]
	print(solve(vertexhas, getedges(edgelist, len(vertexhas)), setsize))

def readints():
	return [int(fld) for fld in input().split()]

def getedges(edgelist, nvert):
	edges = [[] for _ in range(nvert)]
	for (a, b, cost) in edgelist:
		edges[a - 1].append((b - 1, cost))
		edges[b - 1].append((a - 1, cost))
	return edges

def solve(vertexhas, edges, setsize):
	costs = getcost(vertexhas, edges, setsize, 0)
	return bestcost(costs[-1])

def getcost(vertexhas, edges, setsize, source):
	costs = [[float('Inf')] * 2 ** setsize for _ in vertexhas]
	heapset = [[] for _ in range(2 ** setsize)]
	heappush(heapset[vertexhas[source]], (0, source))
	for (curset, heap) in enumerate(heapset):
		while heap:
			(cost, vert) = heappop(heap)
			oldcost = costs[vert][curset]
			if cost < oldcost:
				costs[vert][curset] = cost
				for (newvert, newcost) in edges[vert]:
					heappush(heapset[curset | vertexhas[newvert]], (cost + newcost, newvert))
	return costs

def bestcost(costs):
	costs = list(costs)
	print(costs, file=stderr)
	for i in range(len(costs) - 1, -1, -1):
		j = 1
		while j <= i:
			if j & i:
				costs[i - j] = min(costs[i - j], costs[i])
			j <<= 1
	print(costs, file=stderr)
	return min((max(costs[i], costs[~i]) for i in range(len(costs) // 2)))
main()


import math
import os
import random
import re
import sys
from heapq import *
from itertools import *
from sys import stderr

def main():
	(nvert, nedge, setsize) = readints()
	vertexhas = []
	for _ in range(nvert):
		(nelts, *elts) = readints()
		assert nelts == len(elts)
		vertexhas.append(sum((1 << elt - 1 for elt in elts)))
	edgelist = [readints() for _ in range(nedge)]
	print(solve(vertexhas, getedges(edgelist, len(vertexhas)), setsize))

def readints():
	return [int(fld) for fld in input().split()]

def getedges(edgelist, nvert):
	edges = [[] for _ in range(nvert)]
	for (a, b, cost) in edgelist:
		edges[a - 1].append((b - 1, cost))
		edges[b - 1].append((a - 1, cost))
	return edges

def solve(vertexhas, edges, setsize):
	costs = getcost(vertexhas, edges, setsize, 0)
	return bestcost(costs[-1])

def getcost(vertexhas, edges, setsize, source):
	costs = [[float('Inf')] * 2 ** setsize for _ in vertexhas]
	heapset = [[] for _ in range(2 ** setsize)]
	heappush(heapset[vertexhas[source]], (0, source))
	for (curset, heap) in enumerate(heapset):
		while heap:
			(cost, vert) = heappop(heap)
			oldcost = costs[vert][curset]
			if cost < oldcost:
				costs[vert][curset] = cost
				for (newvert, newcost) in edges[vert]:
					heappush(heapset[curset | vertexhas[newvert]], (cost + newcost, newvert))
	return costs

def bestcost(costs):
	costs = list(costs)
	print(costs, file=stderr)
	for i in range(len(costs) - 1, -1, -1):
		j = 1
		while j <= i:
			if j & i:
				costs[i - j] = min(costs[i - j], costs[i])
			j <<= 1
	print(costs, file=stderr)
	return min((max(costs[i], costs[~i]) for i in range(len(costs) // 2)))
main()


from heapq import *
from itertools import *
from sys import stderr

def main():
	(nvert, nedge, setsize) = readints()
	vertexhas = []
	for _ in range(nvert):
		(nelts, *elts) = readints()
		assert nelts == len(elts)
		vertexhas.append(sum((1 << elt - 1 for elt in elts)))
	edgelist = [readints() for _ in range(nedge)]
	print(solve(vertexhas, getedges(edgelist, len(vertexhas)), setsize))

def readints():
	return [int(fld) for fld in input().split()]

def getedges(edgelist, nvert):
	edges = [[] for _ in range(nvert)]
	for (a, b, cost) in edgelist:
		edges[a - 1].append((b - 1, cost))
		edges[b - 1].append((a - 1, cost))
	return edges

def solve(vertexhas, edges, setsize):
	costs = getcost(vertexhas, edges, setsize, 0)
	return bestcost(costs[-1])

def getcost(vertexhas, edges, setsize, source):
	costs = [[float('Inf')] * 2 ** setsize for _ in vertexhas]
	heapset = [[] for _ in range(2 ** setsize)]
	heappush(heapset[vertexhas[source]], (0, source))
	for (curset, heap) in enumerate(heapset):
		while heap:
			(cost, vert) = heappop(heap)
			oldcost = costs[vert][curset]
			if cost < oldcost:
				costs[vert][curset] = cost
				for (newvert, newcost) in edges[vert]:
					heappush(heapset[curset | vertexhas[newvert]], (cost + newcost, newvert))
	return costs

def bestcost(costs):
	costs = list(costs)
	print(costs, file=stderr)
	for i in range(len(costs) - 1, -1, -1):
		j = 1
		while j <= i:
			if j & i:
				costs[i - j] = min(costs[i - j], costs[i])
			j <<= 1
	print(costs, file=stderr)
	return min((max(costs[i], costs[~i]) for i in range(len(costs) // 2)))
main()


import sys
from collections import defaultdict, deque
from itertools import combinations
import heapq

class PriorityQueue:

	def __init__(self, array=None) -> None:
		if array is None:
			array = []
		self.data = defaultdict(lambda : deque())
		self.heap = []
		self.size = 0
		for el in array:
			self.append(el)

	def top(self):
		if self.size == 0:
			return None
		return (self.heap[0], self.data[self.heap[0]][-1])

	def append(self, element):
		self.size += 1
		if len(element) == 2:
			(p, val) = element
		else:
			(p, val) = (element[0], element[1:])
		if len(self.data[p]) == 0:
			heapq.heappush(self.heap, p)
		self.data[p].appendleft(val)

	def extract(self):
		if self.size == 0:
			return None
		self.size -= 1
		p = self.heap[0]
		val = self.data[p].pop()
		if len(self.data[p]) == 0:
			heapq.heappop(self.heap)
		return (p, val)

class MyGraph:

	def __init__(self, nV=None, k=None) -> None:
		self.V = 0 if nV == None else nV
		self.adjacencyList = defaultdict(lambda : defaultdict(lambda : float('inf')))
		self.fish = [(1 << k) - 1] + [0] * nV
		self.K = k

	def addEdge(self, fromVertex, toVertex, distance=1):
		self.adjacencyList[fromVertex][toVertex] = distance
		self.adjacencyList[toVertex][fromVertex] = distance

	def dijkstra(self, source):
		states = defaultdict(lambda : defaultdict(lambda : float('inf')))
		q = PriorityQueue([(float('inf'), source, self.fish[source])])
		states[source][self.fish[source]] = 0
		while q.size:
			(_, [node, mask]) = q.extract()
			for key in self.adjacencyList[node]:
				now = mask | self.fish[key]
				tmp = states[node][mask] + self.adjacencyList[node][key]
				if tmp < states[key][now]:
					states[key][now] = tmp
					q.append((tmp, key, now))
		return states[self.V]

	def getTime(self):
		states = self.dijkstra(1)
		reached = [bits for bits in states]
		minTime = states[reached.pop()]
		combs = combinations(reached, 2)
		for comb in combs:
			if comb[0] | comb[1] == self.fish[0]:
				minTime = min(minTime, max(states[comb[0]], states[comb[1]]))
		print(minTime)

def main():
	(n, m, k) = map(int, sys.stdin.readline().split())
	graph = MyGraph(n, k)
	for i in range(1, n + 1):
		fishes = list(map(int, sys.stdin.readline().split()))
		fishes.pop(0)
		for fi in fishes:
			graph.fish[i] |= 1 << fi - 1
	for _ in range(m):
		graph.addEdge(*map(int, sys.stdin.readline().split()))
	graph.getTime()
main()