Implement Dijkstra’s algorithm on vertices, where each vertex is a string. Implement the graph using an adjacency list only.

Input Format: The first input is T, the number of test cases. Thereafter, each test case starts with “V E”, where V is the number of vertices and E is the number of edges. The next V lines print the vertex names. Thereafter, each E line contains “u v w” denoting an edge from the vertex named u to the vertex named v with weight w. The next input is Q, the number of queries. The next Q lines are in the form of “u v” asking to print the cost from the vertex named u to the vertex named v.

Output Format: Q lines, each printing the path between the queried vertices. If there is no path, print NIL.

Sample Input

1

7 14

A

B

C

D

E

F

G

A F 12

F A 12

A B 6

B A 6

B C 1

C B 1

C F 3

F C 3

A D 7

D A 7

D E 1

E D 1

E F 1

F E 1

7

A A

A B

A C

A D

A E

A F

A G

Sample Output

0

6

7

7

8

9

-1