Read problems statements in mandarin chinese, russian and vietnamese as well. 

Chef recently learned about finding shortest paths in a bidirectional graph. He has following types of graphs with him and would like to find shortest paths between some given pair of vertices.

There are N cycles in the graph. Let us enumerate them cycle number 1 to N. The i-th cycle contains A_{i} nodes enumerated from 1 to A_{i}.

The nodes of a single cycle are connected to each other in cyclic fashion, i.e. the 1st node is connected to 2nd, 2nd to 3rd, and so on till the last node is connected to the 1st node. All of these edges are weighed.

The cycles are also connected to each other via an edge in a similar cyclic order. The i-th cycle is connected to i % N + 1-th cycle via an edge. This edge is between some vertex v_{1} of i-th cycle and vertex v_{2} of i % N + 1-th cycle and is a weighted edge.

You are given Q queries, each containing four integers v_{1}, c_{1}, v_{2}, c_{2}. You have to find the weight of shortest path between the v_{1}-th vertex of c_{1}-th cycle, and v_{2}-th vertex of c_{2}-th cycle.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases.
First line of each test case contains two space separated integers N, Q denoting the number of cycles in the graph and the number of queries.
Next N lines contain the description of the cycles.
The i-th line describes i-th cycle. First it contains an integer A_{i} denoting the number nodes in the i-th cycle followed by A_{i} integers denoting the weight of edges of the cycle. First integer denotes the weight of edge from node 1 to node 2, from 2 to 3 and so on. Last integer denotes the weight of the edge from node A_{i} to node 1. 
Next N lines describe connections between adjacent cycles. The i-th line contains three space separated integers v_{1}, v_{2}, w denoting that there is an edge of weight w between the v_{1}-th node of i-th cycle and v_{2}-th node of the i % N + 1-th cycle.
Next Q lines describe the queries. Each query is given by four space separated integers v_{1}, c_{1}, v_{2}, c_{2}

------ Output ------ 

For each query, output a single integer corresponding to the total weight of the shortest path. 

------ Constraints ------ 

$1 ≤ T ≤ 5$
$1 ≤ N, Q ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{5}$
$1 ≤ A_{1} + A_{2} + ... + A_{N} ≤ 10^{5}$
$1 ≤ weight of edges ≤ 10^{3}$
$For each query,  c_{1} !=  c_{2}$

------ Subtasks ------ 

$Subtask #1 (10 points): 1 ≤ A_{1} + A_{2} + ... + A_{N} ≤ 10^{3}, 1 ≤ Q ≤ 10^{3}.$
$Subtask #2 (15 points):  All the edges are of weight = 1.$
$Subtask #3 (20 points): c_{1} = 1 for all the queries.$
$Subtask #4 (55 points): Original constraints$

----- Sample Input 1 ------ 
1

3 3

3 1 2 2

2 1 2

3 1 4 1

2 1 2

2 1 5

3 1 3

2 1 1 2

1 1 1 2

3 1 3 3
----- Sample Output 1 ------ 
2

3

5
----- explanation 1 ------ 
Example case 1.
Here is the description of the graph. 

There are 3 cycles. 

Cycle 1: 3 nodes. Edges: (1, 2) = 1, (2, 3) = 2, (3, 1) = 2.
Cycle 2: 2 nodes. Edges: (1, 2) = 1, (2, 1) = 2.
Cycle 3: 3 nodes. Edges: (1, 2) = 1, (2, 3) = 4, (3, 1) = 1.

Connections between adjacent cycles:

Cycle 1 node 2 is connected to Cycle 2 node 1 with edge of weight 2. 
Cycle 2 node 2 is connected to Cycle 3 node 1 with edge of weight 5.
Cycle 3 node 3 is connected to Cycle 1 node 1 with edge of weight 3.

Queries
Best path from node 2 cycle 1 to node 1 cycle 2 is of the cost 2. 
Best path from node 1 cycle 1 to node 1 cycle 2 is: 
edge (1, 2) of cycle 1 + edge (2, 1) between cycles 1 and 2.
Best path from node 3 cycle 1 to node 3 cycle 3 is:
edge (3,1) of cycle 1 + edge (3, 1) between cycles 3 and 1.

Source: codechef | Difficulty: HARD
Tags: Range queries


Solutions:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
	return int(input())

def reads():
	return [int(x) for x in input().split()]
T = read()
for _ in range(T):
	(N, Q) = reads()
	A = []
	W = []
	Scy = []
	for i in range(N):
		line = reads()
		a = line[0]
		w = line[1:]
		aa = a * 2
		scy = [0] * aa
		for j in range(1, aa):
			scy[j] = scy[j - 1] + w[(j - 1) % a]
		Scy.append(scy)
		A.append(a)
		W.append(w)

	def smalldistr(k, i, j):
		scy = Scy[k]
		a = A[k]
		return scy[j] - scy[i] if i <= j else scy[j + a] - scy[i]

	def smalldist(k, i, j):
		return min(smalldistr(k, i, j), smalldistr(k, j, i))
	NN = N * 2
	Lcy = [0] * NN
	Ledges = []
	Vi = [0] * N
	Vo = [0] * N
	for i in range(N):
		(v1, v2, w) = reads()
		(v1, v2) = (v1 - 1, v2 - 1)
		Ledges.append(w)
		Vo[i] = v1
		Vi[(i + 1) % N] = v2
	for i in range(1, NN):
		imod = (i - 1) % N
		Lcy[i] = smalldist(imod, Vi[imod], Vo[imod]) + Lcy[i - 1] + Ledges[imod]

	def largedistr(i, j):
		return Lcy[j] - Lcy[i] if i <= j else Lcy[j + N] - Lcy[i]
	for i in range(Q):
		(v1, c1, v2, c2) = reads()
		(v1, v2, c1, c2) = (v1 - 1, v2 - 1, c1 - 1, c2 - 1)
		dR = smalldist(c1, v1, Vo[c1]) + largedistr(c1, c2) + smalldist(c2, v2, Vi[c2]) - smalldist(c1, Vi[c1], Vo[c1])
		dL = smalldist(c2, v2, Vo[c2]) + largedistr(c2, c1) + smalldist(c1, v1, Vi[c1]) - smalldist(c2, Vi[c2], Vo[c2])
		print(min(dR, dL))


def find_distance(parameters, vertex1, cycle1, vertex2, cycle2):
	if cycle1 == cycle2:
		return find_distance_within_cycle(parameters['edges'][cycle1 - 1], vertex1, vertex2)
	else:
		if cycle1 > cycle2:
			(cycle1, cycle2) = (cycle2, cycle1)
			(vertex1, vertex2) = (vertex2, vertex1)
		clock_path_start = find_distance_within_cycle(parameters['edges'][cycle1 - 1], parameters['cycle_links'][cycle1 - 1][1], vertex1)
		clock_path_end = find_distance_within_cycle(parameters['edges'][cycle2 - 1], parameters['cycle_links'][cycle2 - 1][0], vertex2)
		clock_path_cycle = parameters['links'][cycle2 - 1] - parameters['links'][cycle1 - 1]
		clock_path_inner = parameter['link_inner'][cycle2 - 1] - parameter['link_inner'][cycle1]
		clock_path = clock_path_start + clock_path_cycle + clock_path_inner + clock_path_end
		anti_clock_path_start = find_distance_within_cycle(parameters['edges'][cycle1 - 1], parameters['cycle_links'][cycle1 - 1][0], vertex1)
		anti_clock_path_end = find_distance_within_cycle(parameters['edges'][cycle2 - 1], parameters['cycle_links'][cycle2 - 1][1], vertex2)
		anti_clock_path_cycle = parameters['links'][-1] - clock_path_cycle
		anti_clock_path_inner = parameter['link_inner'][-1] - parameter['link_inner'][cycle2] + parameter['link_inner'][cycle1 - 1]
		anti_clock_path = anti_clock_path_start + anti_clock_path_cycle + anti_clock_path_inner + anti_clock_path_end
		if clock_path < anti_clock_path:
			return clock_path
		return anti_clock_path

def find_distance_within_cycle(cycle, vertex1, vertex2):
	dist1 = abs(cycle[vertex2 - 1] - cycle[vertex1 - 1])
	dist2 = cycle[-1] - dist1
	if dist1 < dist2:
		return dist1
	return dist2
t = int(input())
while t > 0:
	t -= 1
	(n, q) = map(int, input().strip().split())
	cnt = []
	edges = []
	links = [0]
	link_vertex = []
	link_inner = [0]
	cycle_links = []
	for i in range(n):
		inp = list(map(int, input().strip().split()))
		cnt.append(inp.pop(0))
		tmp = [0]
		for j in range(cnt[i]):
			tmp.append(tmp[j] + inp[j])
		edges.append(tmp)
	for i in range(n):
		link = list(map(int, input().strip().split()))
		links.append(links[i] + link.pop(2))
		link_vertex.append(link)
	start_node = link_vertex[-1][1]
	for i in range(n):
		end_node = link_vertex[i][0]
		dist = find_distance_within_cycle(edges[i], start_node, end_node)
		link_inner.append(link_inner[i] + dist)
		cycle_links.append([start_node, end_node])
		start_node = link_vertex[i][1]
	parameter = {'edges': edges, 'cycle_links': cycle_links, 'link_inner': link_inner, 'links': links}
	for _ in range(q):
		(v1, c1, v2, c2) = map(int, input().strip().split())
		print(find_distance(parameter, v1, c1, v2, c2))


t = int(input())
while t > 0:
	(n, q) = [int(i) for i in input().split()]
	g = [[int(i) for i in input().split()] for j in range(n)]
	fg = [0]
	wfg = [0]
	edge = [[int(i) for i in input().split()] for j in range(n)]
	query = [[int(i) for i in input().split()] for j in range(q)]
	for i in range(0, n):
		for j in range(2, g[i][0] + 1):
			g[i][j] = g[i][j] + g[i][j - 1]
	for i in range(n):
		fg.append(edge[i][2])
		s = edge[i - 1][1]
		e = edge[i][0]
		if s < e:
			if s == 1:
				if s == e:
					wfg.append(0)
				else:
					wfg.append(min(g[i][e - 1], g[i][g[i][0]] - g[i][e - 1]))
			else:
				wfg.append(min(g[i][e - 1] - g[i][s - 1], g[i][g[i][0]] - g[i][e - 1] + g[i][s - 1]))
		else:
			s = s + e
			e = s - e
			s = s - e
			if s == 1:
				if s == e:
					wfg.append(0)
				else:
					wfg.append(min(g[i][e - 1], g[i][g[i][0]] - g[i][e - 1]))
			else:
				wfg.append(min(g[i][e - 1] - g[i][s - 1], g[i][g[i][0]] - g[i][e - 1] + g[i][s - 1]))
	for i in range(1, n + 1):
		wfg[i] = wfg[i] + wfg[i - 1]
		fg[i] = fg[i] + fg[i - 1]
		g[i - 1][0] = 0
	for i in range(q):
		source = query[i][0]
		end = query[i][2]
		gs = query[i][1]
		ge = query[i][3]
		if gs > ge:
			gs = gs + ge
			ge = gs - ge
			gs = gs - ge
			source = source + end
			end = source - end
			source = source - end
		gs -= 1
		ge -= 1
		if gs < ge:
			Min1 = fg[ge] - fg[gs] + wfg[ge] - wfg[gs + 1]
			Min2 = fg[n] + wfg[n] - Min1 - (wfg[gs + 1] - wfg[gs] + wfg[ge + 1] - wfg[ge])
			s = source
			e = edge[gs][0]
			if s < e:
				Min1 += min(g[gs][e - 1] - g[gs][s - 1], g[gs][len(g[gs]) - 1] - g[gs][e - 1] + g[gs][s - 1])
			else:
				s = s + e
				e = s - e
				s = s - e
				Min1 += min(g[gs][e - 1] - g[gs][s - 1], g[gs][len(g[gs]) - 1] - g[gs][e - 1] + g[gs][s - 1])
			s = edge[ge - 1][1]
			e = end
			if s < e:
				Min1 += min(g[ge][e - 1] - g[ge][s - 1], g[ge][len(g[ge]) - 1] - g[ge][e - 1] + g[ge][s - 1])
			else:
				s = s + e
				e = s - e
				s = s - e
				Min1 += min(g[ge][e - 1] - g[ge][s - 1], g[ge][len(g[ge]) - 1] - g[ge][e - 1] + g[ge][s - 1])
			s = source
			e = edge[gs - 1][1]
			if s < e:
				Min2 += min(g[gs][e - 1] - g[gs][s - 1], g[gs][len(g[gs]) - 1] - g[gs][e - 1] + g[gs][s - 1])
			else:
				s = s + e
				e = s - e
				s = s - e
				Min2 += min(g[gs][e - 1] - g[gs][s - 1], g[gs][len(g[gs]) - 1] - g[gs][e - 1] + g[gs][s - 1])
			s = edge[ge][0]
			e = end
			if s < e:
				Min2 += min(g[ge][e - 1] - g[ge][s - 1], g[ge][len(g[ge]) - 1] - g[ge][e - 1] + g[ge][s - 1])
			else:
				s = s + e
				e = s - e
				s = s - e
				Min2 += min(g[ge][e - 1] - g[ge][s - 1], g[ge][len(g[ge]) - 1] - g[ge][e - 1] + g[ge][s - 1])
			print(min(Min1, Min2))
	t -= 1


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	graph = []
	sizes = []
	connections = []
	junctions = []
	query = []
	for j in range(n):
		temp_array = [int(k) for k in input().split()]
		sizes.append(temp_array[0])
		for elem in range(2, sizes[j] + 1):
			temp_array[elem] += temp_array[elem - 1]
		graph.append(temp_array[1:])
	for j in range(n):
		temp_array = [int(k) for k in input().split()]
		junctions.append([temp_array[0], temp_array[1]])
		connections.append(temp_array[2])
	for j in range(1, n):
		connections[j] += connections[j - 1]
	for j in range(q):
		temp_array = [int(k) for k in input().split()]
		query.append(temp_array)
	beg = []
	end = []
	new_junction = []
	new_junction.append([junctions[-1][1], junctions[0][0]])
	for j in range(n - 1):
		new_junction.append([junctions[j][1], junctions[j + 1][0]])
	for j in range(n):
		(s, e) = new_junction[j]
		temp_array = []
		if sizes[j] >= 2:
			for z in range(1, sizes[j] + 1):
				fixed = s
				if fixed == z:
					temp_array.append(0)
					continue
				if z == 1:
					m1 = graph[j][fixed - 2]
					m2 = graph[j][-1] - m1
					temp_array.append(min(m1, m2))
					continue
				else:
					m1 = abs(graph[j][fixed - 2] - graph[j][z - 2])
					m2 = abs(graph[j][-1]) - m1
					temp_array.append(min(m1, m2))
					continue
		else:
			temp_array = [0]
		beg.append(temp_array)
		temp_array2 = []
		if sizes[j] >= 2:
			for z in range(1, sizes[j] + 1):
				fixed = e
				if fixed == z:
					temp_array2.append(0)
					continue
				if z == 1:
					m1 = graph[j][fixed - 2]
					m2 = graph[j][-1] - m1
					temp_array2.append(min(m1, m2))
					continue
				else:
					m1 = abs(graph[j][fixed - 2] - graph[j][z - 2])
					m2 = abs(graph[j][-1]) - m1
					temp_array2.append(min(m1, m2))
					continue
		else:
			temp_array2 = [0]
		end.append(temp_array2)
	distances = []
	for j in range(n):
		distances.append(beg[j][new_junction[j][1] - 1])
	new_distances = [distances[0]]
	for j in range(1, n):
		new_distances.append(distances[j] + new_distances[j - 1])
	for Q in range(q):
		if query[Q][1] > query[Q][3]:
			(c1, c2) = (query[Q][3], query[Q][1])
			(v1, v2) = (query[Q][2], query[Q][0])
		else:
			(v1, v2) = (query[Q][0], query[Q][2])
			(c1, c2) = (query[Q][1], query[Q][3])
		if c1 == 1:
			x1 = connections[c2 - 2]
			x2 = connections[-1] - x1
		else:
			x1 = abs(connections[c2 - 2] - connections[c1 - 2])
			x2 = abs(connections[-1] - x1)
		x1 += end[c1 - 1][v1 - 1]
		x1 += beg[c2 - 1][v2 - 1]
		x2 += beg[c1 - 1][v1 - 1]
		x2 += end[c2 - 1][v2 - 1]
		if n > 2:
			if c2 - c1 > 1:
				foo = new_distances[c2 - 2] - new_distances[c1 - 1]
				x1 += foo
				bar = new_distances[-1] - (foo + distances[c1 - 1] + distances[c2 - 1])
				x2 += bar
			if c2 - c1 == 1:
				bar = new_distances[-1] - (distances[c2 - 1] + distances[c1 - 1])
				x2 += bar
			print(min(x1, x2))
		else:
			print(min(x1, x2))


t = int(input())
for test in range(t):
	(n, q) = map(int, input().split())
	cycles = [None]
	for cycle in range(n):
		tmp = list(map(int, input().split()))
		tmpPreSum = [None, 0]
		for i in range(1, tmp[0] + 1):
			tmpPreSum.append(tmp[i] + tmpPreSum[-1])
		cycles.append(tmpPreSum)
	cons = []
	for con in range(n):
		(v1, v2, w) = map(int, input().split())
		cons.append([v1, v2, w])
	conPreSum = [0]
	minDisEdgeToEdge = [None]
	for i in range(n):
		tmpDis = abs(cycles[i + 1][cons[i - 1][1]] - cycles[i + 1][cons[i][0]])
		minDis = min(tmpDis, cycles[i + 1][-1] - tmpDis)
		minDisEdgeToEdge.append(minDis)
		conPreSum.append(conPreSum[-1] + minDis)
		conPreSum.append(conPreSum[-1] + cons[i][2])
	for query in range(q):
		(v1, c1, v2, c2) = map(int, input().split())
		if c1 > c2:
			(v1, v2) = (v2, v1)
			(c1, c2) = (c2, c1)
		tmp = abs(cycles[c1][v1] - cycles[c1][cons[c1 - 1][0]])
		minTmp = min(tmp, cycles[c1][-1] - tmp)
		dis1 = minTmp
		way1 = abs(conPreSum[2 * (c2 - 1)] - conPreSum[c1 * 2 - 1])
		dis1 += way1
		tmp = abs(cycles[c2][v2] - cycles[c2][cons[c2 - 2][1]])
		minTmp = min(tmp, cycles[c2][-1] - tmp)
		dis1 += minTmp
		tmp = abs(cycles[c1][v1] - cycles[c1][cons[c1 - 2][1]])
		minTmp = min(tmp, cycles[c1][-1] - tmp)
		dis2 = minTmp
		way2 = abs(conPreSum[-1] - way1 - minDisEdgeToEdge[c1] - minDisEdgeToEdge[c2])
		dis2 += way2
		tmp = abs(cycles[c2][v2] - cycles[c2][cons[c2 - 1][0]])
		minTmp = min(tmp, cycles[c2][-1] - tmp)
		dis2 += minTmp
		print(min(dis2, dis1))


t = int(input())
while t > 0:
	t = t - 1
	str_arr = input().split(' ')
	n = int(str_arr[0])
	q = int(str_arr[1])
	vec = [[] for i in range(n)]
	how_far = [[] for i in range(n)]
	how_far2 = [[] for i in range(n)]
	for i in range(n):
		str_arr = input().split(' ')
		x = int(str_arr[0])
		for j in range(x):
			vec[i].append(int(str_arr[j + 1]))
			how_far[i].append(int(0))
			how_far2[i].append(int(0))
	initiate = [int(0) for i in range(n)]
	end = [int(0) for i in range(n)]
	worth = [int(0) for i in range(n)]
	for i in range(n):
		str_arr = input().split(' ')
		u = int(str_arr[0])
		vec3 = int(str_arr[1])
		w = int(str_arr[2])
		u = u - 1
		vec3 = vec3 - 1
		end[i] = u
		initiate[(i + 1) % n] = vec3
		worth[i] = w
	for i in range(n):
		siz = len(vec[i])
		x = initiate[i]
		y = end[i]
		temp2 = [int(0) for i in range(siz)]
		temp1 = [int(0) for i in range(siz)]
		for j in range(1, siz):
			temp2[j] = vec[i][j - 1] + temp2[j - 1]
		for j in range(siz - 1, 0, -1):
			temp1[j] = vec[i][j] + temp1[(j + 1) % siz]
		for j in range(siz):
			if j <= x:
				how_far[i][j] = min(temp2[x] - temp2[j], temp2[j] + temp1[x])
			else:
				how_far[i][j] = min(temp2[j] - temp2[x], temp2[x] + temp1[j])
		for j in range(siz):
			if j <= y:
				how_far2[i][j] = min(temp2[y] - temp2[j], temp2[j] + temp1[y])
			else:
				how_far2[i][j] = min(temp2[j] - temp2[y], temp2[y] + temp1[j])
	movement = [int(0) for i in range(n)]
	for i in range(n):
		x = initiate[i]
		y = end[i]
		if i == 0:
			movement[i] = how_far[i][y]
		else:
			movement[i] = how_far[i][y] + movement[i - 1]
	temporary1 = [int(0) for i in range(n)]
	temporary2 = [int(0) for i in range(n)]
	for i in range(1, n):
		temporary1[i] = temporary1[i - 1] + worth[i - 1]
	for i in range(n - 1, 0, -1):
		temporary2[i] = temporary2[(i + 1) % n] + worth[i]
	for i in range(q):
		str_arr = input().split(' ')
		vec1 = int(str_arr[0])
		c1 = int(str_arr[1])
		vec2 = int(str_arr[2])
		c2 = int(str_arr[3])
		vec1 = vec1 - 1
		c1 = c1 - 1
		vec2 = vec2 - 1
		c2 = c2 - 1
		if c1 > c2:
			(c1, c2) = (c2, c1)
			(vec1, vec2) = (vec2, vec1)
		ans = how_far2[c1][vec1] + movement[c2 - 1] - movement[c1] + temporary1[c2] - temporary1[c1] + how_far[c2][vec2]
		if c1 > 0:
			ans = min(ans, how_far[c1][vec1] + movement[c1 - 1] + movement[n - 1] - movement[c2] + temporary1[c1] + temporary2[c2] + how_far2[c2][vec2])
		else:
			ans = min(ans, how_far[c1][vec1] + movement[n - 1] - movement[c2] + temporary1[c1] + temporary2[c2] + how_far2[c2][vec2])
		print(ans)


t = int(input())
while t:
	t -= 1
	(n, q) = list(map(int, input().split()))
	innersums = []
	for i in range(n):
		temp = list(map(int, input().split()))
		innersums.append([0])
		for j in range(temp[0]):
			innersums[i].append(innersums[i][-1] + temp[j + 1])
	b = []
	semicircumferences = [0]
	outersum = [0]
	for i in range(n):
		b.append(list(map(int, input().split())))
		b[i][0] -= 1
		b[i][1] -= 1
		outersum.append(outersum[-1] + b[i][-1])
		if i > 0:
			semicircumferences.append(min(abs(innersums[i][b[i][0]] - innersums[i][b[i - 1][1]]), innersums[i][-1] - abs(innersums[i][b[i][0]] - innersums[i][b[i - 1][1]])))
	semicircumferences[0] = min(abs(innersums[0][b[0][0]] - innersums[0][b[-1][1]]), innersums[0][-1] - abs(innersums[0][b[0][0]] - innersums[0][b[-1][1]]))
	outersum2 = [semicircumferences[0]]
	for i in range(1, n):
		outersum2.append(outersum2[-1] + semicircumferences[i])
	while q:
		q -= 1
		(v1, c1, v2, c2) = list(map(int, input().split()))
		(v1, c1, v2, c2) = (v1 - 1, c1 - 1, v2 - 1, c2 - 1)
		if c2 < c1:
			(c1, v1, c2, v2) = (c2, v2, c1, v1)
		print(min(outersum[c2] - outersum[c1] + outersum2[c2 - 1] - outersum2[c1] + min(abs(innersums[c2][v2] - innersums[c2][b[c2 - 1][1]]), innersums[c2][-1] - abs(innersums[c2][v2] - innersums[c2][b[c2 - 1][1]])) + min(abs(innersums[c1][v1] - innersums[c1][b[c1][0]]), innersums[c1][-1] - abs(innersums[c1][v1] - innersums[c1][b[c1][0]])), outersum[-1] - (outersum[c2] - outersum[c1]) + outersum2[-1] - (outersum2[c2 - 1] - outersum2[c1]) - semicircumferences[c1] - semicircumferences[c2] + min(abs(innersums[c2][v2] - innersums[c2][b[c2][0]]), innersums[c2][-1] - abs(innersums[c2][v2] - innersums[c2][b[c2][0]])) + min(abs(innersums[c1][v1] - innersums[c1][b[c1 - 1][1]]), innersums[c1][-1] - abs(innersums[c1][v1] - innersums[c1][b[c1 - 1][1]]))))


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	data = {}
	conn = [0]
	cycle = [0]
	mini = [0]
	for i in range(n):
		temp = list(map(int, input().split()))
		s = 0
		data[i + 1] = [0]
		for j in temp[1:]:
			s += j
			data[i + 1].append(s)

	def minner(g, x1, x2):
		(x1, x2) = (min(x1, x2), max(x1, x2))
		l1 = data[g][x2 - 1] - data[g][x1 - 1]
		l2 = data[g][-1] - l1
		return min(l1, l2)
	for i in range(1, n + 1):
		(u, v, w) = map(int, input().split())
		conn.append((u, v, w))
	mini.append(minner(1, conn[-1][1], conn[1][0]))
	for i in range(2, n + 1):
		mini.append(minner(i, conn[i - 1][1], conn[i][0]))
	s = 0
	for i in range(1, n + 1):
		s += mini[i] + conn[i][2]
		cycle.append(s)
	for query in range(q):
		(v1, c1, v2, c2) = map(int, input().split())
		if c1 > c2:
			(c1, c2) = (c2, c1)
			(v1, v2) = (v2, v1)
		x = cycle[c2 - 1] - cycle[c1 - 1]
		y = cycle[-1] - x
		x -= mini[c1]
		y -= mini[c2]
		s = minner(c1, v1, conn[c1][0])
		t1 = n if c2 == 1 else c2 - 1
		e = minner(c2, conn[t1][1], v2)
		x += s + e
		t1 = n if c1 == 1 else c1 - 1
		s = minner(c1, conn[t1][1], v1)
		e = minner(c2, v2, conn[c2][0])
		y += s + e
		print(min(x, y))


from itertools import accumulate

def read_test():
	(N, nQ) = list(map(int, input().strip().split()))
	(A, W, WC, Q) = ([], [], [], [])
	for _ in range(N):
		w = list(map(int, input().strip().split()))
		A.append(w[0])
		W.append(w[1:])
	for _ in range(N):
		(v1, v2, w) = list(map(int, input().strip().split()))
		(v1, v2) = (v1 - 1, v2 - 1)
		WC.append((v1, v2, w))
	for _ in range(nQ):
		(v1, c1, v2, c2) = list(map(int, input().strip().split()))
		(v1, c1, v2, c2) = (v1 - 1, c1 - 1, v2 - 1, c2 - 1)
		Q.append((v1, c1, v2, c2))
	return (N, A, W, WC, Q)

def solve(N, A, W, WC, Q):
	sum_sc = list(map(sum, W))
	p_sum_sc = [list(accumulate(W[i])) for i in range(N)]

	def small_dist(c, x, y):
		(x, y) = (min(x, y), max(x, y))
		c1 = (p_sum_sc[c][y - 1] if y > 0 else 0) - (p_sum_sc[c][x - 1] if x > 0 else 0)
		c2 = sum_sc[c] - c1
		return min(c1, c2)
	w_bc = list(map(lambda x: x[2], WC))
	sum_bc = sum(w_bc)
	p_sum_bc = list(accumulate(w_bc))
	v_in = [WC[i - 1][1] for i in range(N)]
	v_out = [WC[i][0] for i in range(N)]
	trav_sc = [small_dist(i, v_in[i], v_out[i]) for i in range(N)]
	sum_trav_sc = sum(trav_sc)
	p_sum_trav_sc = list(accumulate(trav_sc))

	def big_dist(x, y):
		if x == y:
			return sum_bc
		elif x < y:
			return (p_sum_bc[y - 1] if y > 0 else 0) - (p_sum_bc[x - 1] if x > 0 else 0)
		else:
			return sum_bc - big_dist(y, x)

	def trav_dist(x, y):
		if x == y:
			return 0
		elif x < y:
			return p_sum_trav_sc[y - 1] - p_sum_trav_sc[x]
		else:
			return sum_trav_sc - trav_dist(y, x) - trav_sc[y] - trav_sc[x]
	for (v1, c1, v2, c2) in Q:
		if c1 == c2:
			cost1 = small_dist(c1, v1, v2)
			cost2 = sum_bc + sum_trav_sc - trav_sc[c1] + small_dist(c1, v1, v_in[c1]) + small_dist(c1, v2, v_out[c1])
			cost3 = sum_bc + sum_trav_sc - trav_sc[c1] + small_dist(c1, v1, v_out[c1]) + small_dist(c1, v2, v_in[c1])
			cost = min(cost1, cost2, cost3)
			print(cost)
			continue
		if c1 > c2:
			(v1, c1, v2, c2) = (v1, c1, v2, c2)
		cost1 = small_dist(c1, v1, v_out[c1]) + small_dist(c2, v2, v_in[c2]) + big_dist(c1, c2) + trav_dist(c1, c2)
		cost2 = small_dist(c1, v1, v_in[c1]) + small_dist(c2, v2, v_out[c2]) + big_dist(c2, c1) + trav_dist(c2, c1)
		print(min(cost1, cost2))
T = int(input())
for _ in range(T):
	(N, A, W, WC, Q) = read_test()
	solve(N, A, W, WC, Q)


for _ in range(int(input())):
	(N, Q) = map(int, input().split())
	inSumTable = [0 for i in range(N)]
	inJTRight = [[] for i in range(N)]
	MDCTable = [[] for i in range(N)]
	SizeTable = [0 for i in range(N)]
	for i in range(N):
		List = list(map(int, input().split()))
		SizeTable[i] = List[0]
		Sum = 0
		inJTRight[i].append(Sum)
		for j in range(1, SizeTable[i] + 1):
			Sum += List[j]
			inJTRight[i].append(Sum)
		inSumTable[i] = Sum
	outJTRight = []
	LJPts = [0 for i in range(N)]
	RJPts = [0 for i in range(N)]
	for i in range(N):
		(n1, n2, w) = map(int, input().split())
		outJTRight.append(w)
		LJPts[(i + 1) % N] = n2 - 1
		RJPts[i] = n1 - 1
	for i in range(N):
		lp = LJPts[i]
		rp = RJPts[i]
		lpath = 0
		rpath = 0
		for j in range(SizeTable[i]):
			p1 = int(abs(inJTRight[i][j] - inJTRight[i][lp]))
			p2 = inSumTable[i] - p1
			lpath = min(p1, p2)
			p1 = int(abs(inJTRight[i][j] - inJTRight[i][rp]))
			p2 = inSumTable[i] - p1
			rpath = min(p1, p2)
			MDCTable[i].append(tuple([lpath, rpath]))
	fullJTable = [0 for i in range(2 * N + 1)]
	Sum = 0
	for i in range(N):
		r = 2 * i + 1
		l = r + 1
		Sum += MDCTable[i][LJPts[i]][1]
		fullJTable[r] = Sum
		Sum += outJTRight[i]
		fullJTable[l] = Sum
	for i in range(Q):
		(v1, c1, v2, c2) = map(int, input().split())
		v1 -= 1
		v2 -= 1
		c1 -= 1
		c2 -= 1
		if c2 < c1:
			tmp = v1
			v1 = v2
			v2 = tmp
			tmp = c1
			c1 = c2
			c2 = tmp
		path1 = 0
		path2 = 0
		path1 += MDCTable[c1][v1][1] + MDCTable[c2][v2][0]
		path2 += MDCTable[c1][v1][0] + MDCTable[c2][v2][1]
		path1 += fullJTable[c2 * 2] - fullJTable[c1 * 2 + 1]
		path2 += fullJTable[c1 * 2] - fullJTable[0] + (fullJTable[-1] - fullJTable[c2 * 2 + 1])
		minPath = min(path1, path2)
		print(minPath)


for t in range(int(input())):
	(n, q) = map(int, input().split())
	arr = [[]] * n
	arr1 = [[]] * n
	for i in range(n):
		a = list(map(int, input().split()))
		arr[i] = a
		a = a[1:]
		arr1[i] = a
	w = [[]] * n
	for i in range(n):
		a = list(map(int, input().split()))
		w[i] = a
	query = [[]] * q
	for i in range(q):
		a = list(map(int, input().split()))
		query[i] = a
	main1 = [[]] * n
	main2 = [[]] * n
	for i in range(n):
		v1 = w[i][0]
		v2 = w[i - 1][1]
		main = []
		sum1 = 0
		for j in range(arr[i][0]):
			sum1 += arr1[i][j]
		sum2 = 0
		for j in range(arr[i][0]):
			sum2 += arr1[i][(v1 - 1 + j) % arr[i][0]]
			if sum2 < sum1 - sum2:
				main.append(sum2)
			else:
				main.append(sum1 - sum2)
		main1[i] = main
		m = i
		main = []
		sum1 = 0
		sum2 = 0
		for j in range(arr[i][0]):
			sum1 += arr1[i][j]
		for j in range(arr[m][0]):
			sum2 += arr1[m][(v2 - 1 + j) % arr[m][0]]
			if sum2 < sum1 - sum2:
				main.append(sum2)
			else:
				main.append(sum1 - sum2)
		main2[i] = main
	cycle1 = [0] * n
	cycle1[0] = w[0][2]
	v1v2 = [0] * n
	y = w[-1][1] - w[0][0]
	x = -1 - y
	v1v2[0] = main2[0][x]
	for i in range(1, n - 1):
		y = w[i - 1][1] - w[i][0]
		x = -1 - y
		weight = w[i][2]
		cycle1[i] = cycle1[i - 1] + main2[i][x] + weight
		v1v2[i] = main2[i][x]
		y = w[-2][1] - w[-1][0]
		x = -1 - y
		v1v2[n - 1] = main2[-1][x]
	sumall = cycle1[-2] + w[-1][2] + v1v2[-1] + v1v2[0]
	for i in range(q):
		v1 = query[i][0]
		c1 = query[i][1]
		v2 = query[i][2]
		c2 = query[i][3]
		if c1 > c2:
			y = v1 - w[c1 - 2][1]
			x = y - 1
			sum1 = main2[c1 - 1][x]
			y = v2 - w[c2 - 1][0]
			x = y - 1
			sum1 += main1[c2 - 1][x]
		else:
			y = v1 - w[c1 - 1][0]
			x = y - 1
			sum1 = main1[c1 - 1][x]
			y = v2 - w[c2 - 2][1]
			x = y - 1
			sum1 += main2[c2 - 1][x]
		if c1 == 1 or c2 == 1:
			sum2 = cycle1[abs(c1 - c2) - 1]
		elif c1 > c2:
			sum2 = abs(cycle1[c1 - 2] - cycle1[c2 - 2]) - v1v2[c2 - 1]
		else:
			sum2 = abs(cycle1[c1 - 2] - cycle1[c2 - 2]) - v1v2[c1 - 1]
		sum1 += sum2
		if c1 > c2:
			y = v1 - w[c1 - 1][0]
			x = y - 1
			sum3 = main1[c1 - 1][x]
			y = v2 - w[c2 - 2][1]
			x = y - 1
			sum3 += main2[c2 - 1][x]
		else:
			y = v1 - w[c1 - 2][1]
			x = y - 1
			sum3 = main2[c1 - 1][x]
			y = v2 - w[c2 - 1][0]
			x = y - 1
			sum3 += main1[c2 - 1][x]
		sum2 = sumall - sum2 - v1v2[c1 - 1] - v1v2[c2 - 1]
		sum3 += sum2
		if sum1 < sum3:
			print(sum1)
		else:
			print(sum3)


from collections import defaultdict as dd
from random import randint as rad

def get(a, i, j):
	ans = 0
	if i > j:
		(i, j) = (j, i)
	if i != j:
		return min(abs(a[j - 1] - a[i - 1]), abs(a[-1] - a[j - 1] + a[i - 1]))
	elif i == j:
		return 0
for _ in range(int(input())):
	(n, q) = [int(i) for i in input().split()]
	nodes = []
	c_sum = dd(list)
	c_left = dd(int)
	c_right = dd(int)
	ck = []
	for j in range(n):
		a = [int(i) for i in input().split()]
		ck.append(a)
		nodes.append(a[0])
		su = a[1:]
		for i in range(1, a[0]):
			su[i] += su[i - 1]
		c_sum[j] = [0] + su
	e = []
	for i in range(1, n + 1):
		a = [int(j) for j in input().split()]
		c_right[i] = a[0]
		c_left[i + 1 if i + 1 <= n else 1] = a[1]
		e.append(a[2])
	c_dis = [0] + e[:]
	diff = [0]
	for i in range(1, len(e) + 1):
		c_dis[i] += c_dis[i - 1] + get(c_sum[i % n], c_left[i + 1 if i + 1 <= n else 1], c_right[i + 1 if i + 1 <= n else 1])
		diff.append(get(c_sum[i % n], c_left[i + 1 if i + 1 <= n else 1], c_right[i + 1 if i + 1 <= n else 1]))
	diff[0] = diff[-1]
	for i in range(q):
		que = [int(i) for i in input().split()]
		if que[1] > que[3]:
			(que[0], que[2]) = (que[2], que[0])
			(que[1], que[3]) = (que[3], que[1])
		anr = abs(c_dis[que[1] - 1] - c_dis[que[3] - 1]) - diff[que[3] - 1] + (get(c_sum[que[1] - 1], c_right[que[1]], que[0]) + get(c_sum[que[3] - 1], c_left[que[3]], que[2]))
		anl = abs(c_dis[-1] - c_dis[que[3] - 1]) + c_dis[que[1] - 1] - diff[que[1] - 1] + (get(c_sum[que[3] - 1], c_right[que[3]], que[2]) + get(c_sum[que[1] - 1], c_left[que[1]], que[0]))
		print(min(anr, anl))


def main():
	for t in range(int(input())):
		(N, Q) = map(int, input().split())
		E = [list(map(int, input().split()))[1:] for i in range(N)]
		(L, R, W) = ([0] * N, [0] * N, [0] * N)
		for i in range(N):
			(v1, v2, W[i]) = map(int, input().split())
			(R[i], L[(i + 1) % N]) = (v1 - 1, v2 - 1)

		def filldist(Ei, src, dist):
			n = len(Ei)
			nxt = lambda i: i + 1 if i < n - 1 else 0
			prv = lambda i: i - 1 if i > 0 else n - 1
			d = 0
			cur = nxt(src)
			while cur != src:
				d += Ei[prv(cur)]
				dist[cur] = d
				cur = nxt(cur)
			d = 0
			cur = prv(src)
			while cur != src:
				d += Ei[cur]
				dist[cur] = min(dist[cur], d)
				cur = prv(cur)
		Ldist = [[0] * len(Ei) for Ei in E]
		Rdist = [[0] * len(Ei) for Ei in E]
		for i in range(N):
			filldist(E[i], L[i], Ldist[i])
			filldist(E[i], R[i], Rdist[i])
		jump = [Rdist[i][L[i]] + W[i] for i in range(N)]
		pre = [0] * (N + 1)
		for i in range(N):
			pre[i] = pre[i - 1] + jump[i]
		for q in range(Q):
			(v1, c1, v2, c2) = map(int, input().split())
			(v1, c1, v2, c2) = (v1 - 1, c1 - 1, v2 - 1, c2 - 1)
			if c2 < c1:
				(v1, c1, v2, c2) = (v2, c2, v1, c1)
			dist1 = Rdist[c1][v1] + W[c1] + pre[c2 - 1] - pre[c1] + Ldist[c2][v2]
			dist2 = Rdist[c2][v2] + W[c2] + pre[N - 1] - pre[c2] + pre[c1 - 1] + Ldist[c1][v1]
			ans = min(dist1, dist2)
			print(ans)
main()


import numpy as np

def solve(a, z, qq):
	for (i, aa) in enumerate(a):
		aa = np.array([0] + aa, dtype=np.int64)
		a[i] = np.cumsum(aa)

	def inDist(c, v, w):
		if v > w:
			(v, w) = (w, v)
		aa = a[c]
		d = aa[w] - aa[v]
		rr = min(d, aa[-1] - d)
		return rr
	zz = [0]
	for (i, (v, w, ll)) in enumerate(z):
		zz += [inDist(i, v, z[i - 1][1])]
		zz += [ll]
	zz = np.array(zz, dtype=np.int64)
	zz = np.cumsum(zz)

	def cDist(c, d):
		ret = zz[2 * d] - zz[2 * c + 1]
		if d < c:
			ret += zz[-1]
		return ret

	def tDist(v0, c0, v1, c1):
		if c0 == c1:
			return inDist(c0, v0, v1)
		a = cDist(c0, c1) + inDist(c0, v0, z[c0][0]) + inDist(c1, v1, z[c1 - 1][1])
		b = cDist(c1, c0) + inDist(c1, v1, z[c1][0]) + inDist(c0, v0, z[c0 - 1][1])
		return min(a, b)
	ret = []
	for (v0, c0, v1, c1) in qq:
		ret += [tDist(v0 - 1, c0 - 1, v1 - 1, c1 - 1)]
	return ret
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	(n, q) = map(int, f.readline().split())
	a = []
	for i in range(n):
		a += [list(map(int, f.readline().split()))[1:]]
	z = []
	for i in range(n):
		zz = list(map(int, f.readline().split()))
		zz[0] -= 1
		zz[1] -= 1
		z += [zz]
	qq = []
	for i in range(q):
		qq += [list(map(int, f.readline().split()))]
	sol = solve(a, z, qq)
	for s in sol:
		print(s)