// Justin Almazan
// 7/23/2025
// Solution to 2025 CP SI @ UCF Contest 5 Problem: An Optimized Lunch

#include <bits/stdc++.h>
using namespace std;

const int INF = 1'000'000'000;
const int MAXN = 302;

int tt, n, qq, d[MAXN][MAXN];

int main() {

    // Number of test cases
    cin >> tt;

    // Process test cases
    while (tt--) {

        // Get number of locations and groups
        cin >> n >> qq;

        // Get the names of the locations and map to indexes
        map<string, int> mapInd, mapTime;

        for (int i = 0; i < n; i++) {
            string s; int time; cin >> s >> time;
            mapInd[s] = i;
            mapTime[s] = time;
        }

        // Get the adjacency matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> d[i][j];
                if (d[i][j] == -1) d[i][j] = INF;
            }
        }

        // Run Floyd-Warshall to get the lowest distances from any i to any j
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++) 
                for (int j = 0; j < n; j++)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

        // Process queries
        while (qq--) {

            // Get starting + ending string and number of lunch spots
            int numLunch;
            string start, end;
            cin >> start >> end >> numLunch;

            // Convert to indexes
            int si = mapInd[start], ei = mapInd[end];

            pair<int, string> res = {INF, "A"};

            // Get all midpoints
            while (numLunch--) {

                // Get the name of the lunch spot and convert to its index
                string s;
                cin >> s;
                int mi = mapInd[s];
                int time = mapTime[s];

                // Total time is s->m + time it takes to eat + m->e
                res = min(res, {d[si][mi] + mapTime[s] + d[mi][ei], s});
            }

            // Print answer
            cout << res.second << " " << res.first << endl;
        }
    }

    return 0;
}