# Author: Christian Lim
# Date: July 24, 2025

import sys

input = sys.stdin.read


def solve():
    data = input().split()
    idx = 0
    INF = 10**12
    c = int(data[idx])
    idx += 1
    results = []
    for _ in range(c):
        n, g = int(data[idx]), int(data[idx + 1])
        idx += 2
        loc_index = {}
        lunch_time = []
        names = []
        for i in range(n):
            name = data[idx]
            time = int(data[idx + 1])
            loc_index[name] = i
            lunch_time.append(time)
            names.append(name)
            idx += 2
        dist = [[INF] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                val = int(data[idx])
                if val != -1:
                    dist[i][j] = val
                if i == j:
                    dist[i][j] = 0
                idx += 1
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
        for _ in range(g):
            start, end, d = data[idx], data[idx + 1], int(data[idx + 2])
            idx += 3
            lunch_options = data[idx : idx + d]
            idx += d
            u, v = loc_index[start], loc_index[end]
            min_total = INF
            for lunch_spot in lunch_options:
                l = loc_index[lunch_spot]
                total_time = dist[u][l] + lunch_time[l] + dist[l][v]
                min_total = min(min_total, total_time)
            results.append(str(min_total))
    print("\n".join(results))


solve()