#include "pch.h"
#include <iostream>
#include <string>
#include <limits.h>
#include <limits.h>
using namespace std;

struct neighbour
{
    int numberofCity;
    int distance;
};
class Node
{
private:
    string name;
    int countOfNeighbours;
    neighbour *neightbours;
public:
    void getinput()
    {

        cin >> name;

        cin >> countOfNeighbours;
        neightbours = new neighbour[countOfNeighbours];
        for (int i = 0; i < countOfNeighbours; i++)
        {
            cin >> neightbours[i].numberofCity;
            neightbours[i].numberofCity -= 1;
            cin >> neightbours[i].distance;
        }
    }
    void deleteNode()
    {
        delete neightbours;
    }
    string returnName() { return name; }
    neighbour returnNeighbours(int i){ return neightbours[i]; }
    int returncountOfNeighbours() { return countOfNeighbours; }


};
class Graph
{
private:
    int countofCities;
    Node *cities;
public:
    void SetNodes()
    {

        cin >> countofCities;
        cities = new Node[countofCities];
        for (int i = 0; i < countofCities; i++)
        {
            cities[i].getinput();
        }
    }
    int returnIDofCity(string searchName)
    {
        int l;
        for (int i = 0; i < countofCities; i++)
        {
            if (cities[i].returnName() == searchName)
                l = i;
        }
        return l;
    }
    int ReturnNumberOfCities() { return countofCities; }
    Node getNode(int i) { return cities[i]; }

    void del()
    {
        for (int i = 0; i < countofCities; i++)
            {
                cities[i].deleteNode();
            }

    }
};
struct heapNode
{
    private:
        int number;
        int costs;
    public:
        void SetNode(int num, int cos)
        {
            number = num;
            costs = cos;
        }
        int getCost() { return costs; }
        int getNumber() { return number; }
};
class Heap
{
private:
    int heap_size;
    int capacity;
    heapNode *heaparray;
public:
    Heap(int cap)
    {
        heap_size = 0;
        capacity = cap;
        heaparray = new heapNode[capacity];
    }
    int parent(int i) { return (i - 1) / 2; }
    int left(int i) { return (2 * i + 1); }
    int right(int i) { return (2 * i + 2); }
    void swapNodes(heapNode *a, heapNode *b)
    {
        heapNode *tmp = new heapNode();
        *tmp = *a;
        *a = *b;
        *b = *tmp;
    }
    void insert(heapNode *node)
    {
        if (heap_size == capacity)
            return;

        heap_size++;
        int i = heap_size - 1;
        heaparray[i] = *node;

        while (i != 0 && heaparray[parent(i)].getCost() > heaparray[i].getCost())
        {
            swapNodes(&heaparray[parent(i)], &heaparray[i]);
            i = parent(i);
        }
    }
    heapNode getMin()
    {
        heapNode *tmp = new heapNode();
        *tmp = heaparray[0];
        if (heap_size == 1)
        {
            heaparray[heap_size - 1].SetNode(INT_MIN, INT_MIN);
            heap_size--;
        }
        if (heap_size > 1)
        {
            swapNodes(&heaparray[0], &heaparray[heap_size - 1]);
            heaparray[heap_size - 1].SetNode(INT_MIN, INT_MIN);
            heap_size--;
            repairHeap(0);
        }

        return *tmp;
    }

    void repairHeap(int i)
    {
        int l = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < heap_size && heaparray[left].getCost() < heaparray[i].getCost())
            l = left;
        if (right < heap_size && heaparray[right].getCost() < heaparray[l].getCost())
            l = right;
        if (l != i)
        {
            swapNodes(&heaparray[i], &heaparray[l]);
            repairHeap(l);
        }

    }
    void printallnodes()
    {
        for (int i = 0; i < heap_size; i++)
        {
            cout << heaparray[i].getNumber() << " <- Miasto " << heaparray[i].getCost() << endl;
        }
    }
    bool isEmpty()
    {
        if (heap_size > 0)
        {
            return false;
        }
        else return true;
    }
    void del()
    {
        delete heaparray;
    }

};
void Dijkstra(string startNode, string stopNode, Graph *graph)
{
    int nodesCount = graph->ReturnNumberOfCities();
    int startPoint = graph->returnIDofCity(startNode);
    int stopPoint = graph->returnIDofCity(stopNode);
    bool *isVisited = new bool[nodesCount];
    int *distance = new int [nodesCount];
    int *fromNode = new int [nodesCount];
    int currentNode;
    Heap *heap = new Heap(nodesCount);
    heapNode *tmp;
    for (int i = 0; i < nodesCount; i++)
    {
        isVisited[i] = false;
        distance[i] = INT_MAX;
        fromNode[i] = -1;
    }
    currentNode=  startPoint ;
    distance[currentNode] = 0;
    isVisited[currentNode] = true;
    heapNode *node = new heapNode();
    node->SetNode(startPoint, 0);
    heap->insert(node);
    while (!heap->isEmpty())
    {
        heapNode curr = heap->getMin();
        currentNode = curr.getNumber();
        isVisited[currentNode] = true;
        Node city = graph->getNode(currentNode);
        int numOfNeigh = city.returncountOfNeighbours();
        for (int i = 0; i < numOfNeigh; i++)
        {
            neighbour somsiad = city.returnNeighbours(i);

            if (!isVisited[somsiad.numberofCity])
            {
                node->SetNode(somsiad.numberofCity, somsiad.distance + distance[currentNode]);
                heap->insert(node);
            }
            if (distance[somsiad.numberofCity] > somsiad.distance + distance[currentNode])
            {
                distance[somsiad.numberofCity] = somsiad.distance + distance[currentNode];
                fromNode[currentNode];
            }

        }
    }
    cout << distance[stopPoint];
    heap->del();
    delete heap;
}

int main()
{

    int testcount, pathToFind;
    string startNode, stopNode;
    cin >> testcount;
    int i = 0;
    while (i < testcount)
    {
        Graph *graph = new Graph();
        graph->SetNodes();
        //graph->printGraph();
        cin >> pathToFind;
        for (int j = 0; j < pathToFind; j++)
        {
            cin >> startNode >> stopNode;
            Dijkstra(startNode, stopNode, graph);
            cout << endl;
        }
        graph->del();
        delete graph;
        i++;
    }

}