Chef and Cycled Cycles

All submissions for this problem are available.
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 ith 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 ith cycle is connected to i % N + 1th cycle via an edge. This edge is between some vertex v_{1} of ith cycle and vertex v_{2} of i % N + 1th 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 ith line describes ith cycle. First it contains an integer A_{i} denoting the number nodes in the ith 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 ith 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 ith cycle and v_{2}th node of the i % N + 1th 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
Example
Input: 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 Output: 2 3 5
Explanation
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.
Author:  berezin 
Tester:  alex_2oo8 
Editorial  https://discuss.codechef.com/problems/CHEFCCYL 
Tags  berezin, medium, oct17, prefixsums 
Date Added:  24112015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 