Problem Z
Single source shortest path, safe path

Kattis needs to get somewhere as soon as possible. However, she also wants that the path that she takes to be safe too. She deems that paths that use not more than $\textbf{k}$ junctions to be safe paths. Given a map containing $\textbf{V}$ junctions with weighted edges denoting the time (in minutes) needed to traverse between junctions, a start junction $\textbf{s}$, a destination junction $\textbf{t}$, and a limit of number of junctions $\textbf{k}$, return the minimum amount of time that Kattis needs to go from $\textbf{s}$ to $\textbf{t}$, using at most $\textbf{k}$ junctions (inclusive of $\textbf{s}$ and $\textbf{t}$).

Input

Input starts with an integer $TC\: (1 \le TC \le 10)$, denoting number of test cases.

Each test case starts with a newline. The second line contains an integer denoting the number of junctions $V\: (2 \le V \le 1\, 000)$. Then followed by $V$ lines. Each of these lines starts with an integer $X$ denoting the number of edges from that junction, followed by $X$ pairs of integers “vertex weight” ($0 \le $ vertex $ < V$ and $0 \le $ weight $ \le 10^{5}$). The total number of edges will not exceed $400\, 000$. Afterwards, an integer denoting the number of queries $Q\: (1 \le Q \le 20)$ will be given. Each query is of the format “$s$ $t$ $k$”, $(0 \le s,\: t < V)$, $(1 \le k \le \min (V,\: 30))$, where all of $s, t, k$ are integers.

Output

For each query, print the required answer in one line. If the is no answer, print “$-1$”.

Please separate the output of two test cases with a single line.

Explanation

The sample test case $1$ can be visualized as follows:

Query$(0, 3, 4)$: If Kattis’s current position is at vertex $\textbf{s}$ = $0$, and the destination is at vertex $\textbf{t}$ = $3$, and Kattis can use up to $\textbf{k}$ = $4$ junctions, then the quickest way is this path: $0 \rightarrow 1 \rightarrow 2 \rightarrow 3$ with total estimated traveling time of: $2+3+7 = 12$ minutes.

However if we have Query$(0, 3, 3)$, then path: $0 \rightarrow 1 \rightarrow 2 \rightarrow 3$ shown earlier is invalid as it uses $4$ junctions as this time Kattis can only use up to $\textbf{k}$ = $3$ junctions. The valid shortest path from $\textbf{s}$ = $0$ to $\textbf{t}$ = $3$ that uses no more than $\textbf{k}$ = $3$ junctions is path: $0 \rightarrow 3$ with total estimated traveling time of: $15$ minutes. This path is $3$ minutes longer than the true shortest path without Kattis’s restriction of not crossing more than $\textbf{k}$ junctions but it is now the correct solution.

The answer for Query$(0, 3, 2)$ is also $15$ minutes.

Subtasks

1. $\textbf{(30 points)}$: The maps will be undirected weighted trees, $1 \le TC \le 10$, $1 \le V \le 30$, $1 \le Q \le 10$, $K\: =\: V$

2. $\textbf{(30 points)}$: The maps will be directed graphs, $1 \le TC \le 10$, $1 \le V \le 30$, $1 \le E \le 1\, 500$, $1 \le Q \le 10$, $K\: =\: V$

3. $\textbf{(40 points)}$: $1 \le TC \le 10$, $1 \le V \le 1\, 000$, $1 \le E \le 200\, 000$, $1 \le Q \le 20$, $K\: =\: \min (V,\: 30)$

2

4
3 1 2 2 9 3 15
1 2 3
2 0 1 3 7
0
2
0 3 4
0 3 3

4
3 1 2 2 9 3 15
1 2 3
2 0 1 3 7
0
1
0 3 2

12
15

15