// Arup Guha
// 7/24/2025
// Solution to 2025 SI@UCF Programming Contest Camp Contest #5 Problem: An Optimized Lunch

import java.util.*;

public class lunch {

	final public static int INF = 1000000000;

	public static void main(String[] args) {
	
		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();
		
		for (int loop=0; loop<nC; loop++) {
		
			int n = stdin.nextInt();
			int q = stdin.nextInt();
			
			HashMap<String,Integer> map = new HashMap<String,Integer>();
			int[] times = new int[n];
			
			// Read rides, times
			for (int i=0; i<n; i++) {
				String ride = stdin.next();
				times[i] = stdin.nextInt();
				map.put(ride, i);
			}
			
			// Read in adjacency matrix.
			int[][] d = new int[n][n];
			for (int i=0; i<n; i++) {
				for (int j=0; j<n; j++) {
					d[i][j] = stdin.nextInt();
					if (d[i][j] == -1) d[i][j] = INF;
				}
			}
			
			// Run Floyd-Warshall's
			for (int k=0; k<n; k++)
				for (int i=0; i<n; i++)
					for (int j=0; j<n; j++)
						d[i][j] = Math.min(d[i][j], d[i][k]+d[k][j]);
			
			// Do queries.
			for (int i=0; i<q; i++) {
			
				// Get start and end location indexes.
				String start = stdin.next();
				String end = stdin.next();
				int numLunch = stdin.nextInt();
				int s = map.get(start);
				int e = map.get(end);
				
				// Will be overwritten.
				int res = INF;
				
				// Try each lunch place.
				for (int j=0; j<numLunch; j++) {
				
					// Get it and find index.
					String tmp = stdin.next();
					int mid = map.get(tmp);
					
					// Time from s to mid, mid to e, and time to eat...
					res = Math.min(res, d[s][mid]+d[mid][e]+times[mid]);
				}
				
				// Ta da!
				System.out.println(res);
			}
		}
	}
}