TSHPATH

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define inf 0xffFFffFF
#define N 10001

short nodes, paths;
short viz[N], ord[N];
unsigned int*** list, dist[N];
char name[N][11];

inline int cmp(const void* a, const void* b)
{
    return strcmp(name[*((const short*)a)], name[*((const short*)b)]);
}

short getindex(const char* string)
{
    short lo = 1, hi = nodes, mid, res;
    while (lo <= hi) {
        mid = (lo + hi) / 2;
        res = strcmp(string, name[ord[mid]]);
        if (!res) {
            return ord[mid];
        } else if (res > 0) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return 0;
}

void read()
{
    short i, j, nbs, nb;
    unsigned int cst;
    char tmp[11];
    scanf("%hd", &nodes);
    list = (unsigned int***) malloc((nodes + 1) * sizeof(unsigned int**));
    for (i = 1; i <= nodes; ++i) {
        scanf("%s\n%hd", name[i], &nbs);
        ord[i] = i;
        list[i] = (unsigned int**) malloc((nbs + 1) * sizeof(unsigned int*));
        list[i][0] = (unsigned int*) malloc(sizeof(unsigned int));
        list[i][0][0] = nbs;
        for (j = 1; j <= nbs; ++j) {
            scanf("%hd %u", &nb, &cst);
            list[i][j] = (unsigned int*) malloc(2 * sizeof(unsigned int));
            list[i][j][0] = nb;
            list[i][j][1] = cst;
        }
    }
    qsort(ord + 1, nodes, sizeof(short), cmp);
    scanf("%hd", &paths);
}

void process()
{
    short i, j, src, dest, var, flag;
    unsigned int min;
    char tmp[11];
    for (i = 0; i < paths; ++i) {
        scanf("%s", tmp);
        src = getindex(tmp);
        scanf("%s", tmp);
        dest = getindex(tmp);
        memset(viz, 0, (nodes + 1) * sizeof(short));
        memset(dist, 0xFF, (nodes + 1) * sizeof(unsigned int));
        dist[src] = 0;
        var = src;
        do {
            viz[var] = 1;
            for (j = 1; j <= list[var][0][0]; ++j) {
                if (dist[var] + list[var][j][1] < dist[list[var][j][0]]) {
                    dist[list[var][j][0]] = dist[var] + list[var][j][1];
                }
            }
            flag = 0;
            min = inf;
            for (j = 1; j <= nodes; ++j) {
                if (!viz[j] && dist[j] < min) {
                    min = dist[j];
                    var = j;
                    flag = 1;
                }
            }
        } while (flag);
        printf("%u\n", dist[dest]);
    }
}

int main()
{
    short tests;
    //freopen("shpath.in", "rt", stdin);
    for (scanf("%hd", &tests); tests; --tests) {
        read();
        process();
        free(list);
    }
    return 0;
}