#include <iostream>
#include <utility>
#include <set>
#include <vector>
#include <string>
#include <map>
using namespace std;
typedef int btype; //basic type to be used overall
typedef pair<btype,btype> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define INF 99999999
btype dijkstra(const vvpii &G, btype start, btype target)
{
//vector to store keys
vector<btype> keys(G.size(),INF); //initialize all keys with INF
keys[start] = 0; //initialize key of start as 0
//NOW MAKE HEAP,we use set for heap using its property as its a red-blk tree implementation
set <pii> Q;
btype i;
for(i = 1;i<=G.size();i++) //PUT ALL VERTICES IN HEAP
{
if(i!=start)
Q.insert({INF,i});
}
Q.insert({0,start}); //{key,vertex} is a pair
while(!Q.empty())
{
pii top = *(Q.begin()); //EXTACT-MIN
btype u = top.second, key = top.first;
Q.erase(Q.begin()); //DELETE-MIN
if(u == target) //REACHED THE DESTINATION
break;
//FOR ALL NEIGHBOURS, PERFORM RELAX
for(vpii::const_iterator it = G[u].begin(); it != G[u].end(); it++)
{
btype v= (*it).first,cost = (*it).second; //edge cost
if(key + cost < keys[v]) //RELAX if relaxation can be done
{
Q.erase(Q.find({keys[v],v}));
keys[v] = key + cost;
Q.insert({keys[v],v});
}
}
}
return keys[target];
}
int main()
{
int t;
ios::sync_with_stdio(false);
cin>>t;
while(t--)
{
map <string,int> nametoindex;
btype i,j,n;
btype u,v,w,neighbours;
string name;
//GRAPH INPUT
cin>>n;
vvpii G(n+1,vpii()); //0 --> n cities
for(u=1;u<=n;u++)
{
//G.push_back(vpii());
cin>>name;
cin>>neighbours;
nametoindex[name] = u;
for(j=1;j<=neighbours;j++)
{
cin>>v>>w;
G[u].push_back(make_pair(v,w));
}
}
//GRAPH INPUT COMPLETED
//DIJ INPUT
cin>>n;//no of queries
string start,target;
for(i=1;i<=n;i++)
{
cin>>start>>target;
u = nametoindex[start];
v = nametoindex[target];
cout<<dijkstra(G,u,v)<<"\n";
}
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dXRpbGl0eT4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPG1hcD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdHlwZWRlZiBpbnQgYnR5cGU7IC8vYmFzaWMgdHlwZSB0byBiZSB1c2VkIG92ZXJhbGwKdHlwZWRlZiBwYWlyPGJ0eXBlLGJ0eXBlPiBwaWk7CnR5cGVkZWYgdmVjdG9yPHBpaT4gdnBpaTsKdHlwZWRlZiB2ZWN0b3I8dnBpaT4gdnZwaWk7CiNkZWZpbmUgSU5GIDk5OTk5OTk5CgpidHlwZSBkaWprc3RyYShjb25zdCB2dnBpaSAmRywgYnR5cGUgc3RhcnQsIGJ0eXBlIHRhcmdldCkKewogICAgLy92ZWN0b3IgdG8gc3RvcmUga2V5cwogICAgdmVjdG9yPGJ0eXBlPiBrZXlzKEcuc2l6ZSgpLElORik7IC8vaW5pdGlhbGl6ZSBhbGwga2V5cyB3aXRoIElORgogICAga2V5c1tzdGFydF0gPSAwOyAvL2luaXRpYWxpemUga2V5IG9mIHN0YXJ0IGFzIDAKICAgIC8vTk9XIE1BS0UgSEVBUCx3ZSB1c2Ugc2V0IGZvciBoZWFwIHVzaW5nIGl0cyBwcm9wZXJ0eSBhcyBpdHMgYSByZWQtYmxrIHRyZWUgaW1wbGVtZW50YXRpb24KICAgIHNldCA8cGlpPiBROwogICAgYnR5cGUgaTsKICAgIGZvcihpID0gMTtpPD1HLnNpemUoKTtpKyspIC8vUFVUIEFMTCBWRVJUSUNFUyBJTiBIRUFQCiAgICB7CiAgICAgICAgaWYoaSE9c3RhcnQpCiAgICAgICAgICAgIFEuaW5zZXJ0KHtJTkYsaX0pOwogICAgfQogICAgUS5pbnNlcnQoezAsc3RhcnR9KTsgLy97a2V5LHZlcnRleH0gaXMgYSBwYWlyCiAgICB3aGlsZSghUS5lbXB0eSgpKQogICAgewogICAgICAgIHBpaSB0b3AgPSAqKFEuYmVnaW4oKSk7IC8vRVhUQUNULU1JTgogICAgICAgIGJ0eXBlIHUgPSB0b3Auc2Vjb25kLCBrZXkgPSB0b3AuZmlyc3Q7CiAgICAgICAgUS5lcmFzZShRLmJlZ2luKCkpOyAvL0RFTEVURS1NSU4KCiAgICAgICAgaWYodSA9PSB0YXJnZXQpIC8vUkVBQ0hFRCBUSEUgREVTVElOQVRJT04KICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgLy9GT1IgQUxMIE5FSUdIQk9VUlMsIFBFUkZPUk0gUkVMQVgKICAgICAgICBmb3IodnBpaTo6Y29uc3RfaXRlcmF0b3IgaXQgPSBHW3VdLmJlZ2luKCk7IGl0ICE9IEdbdV0uZW5kKCk7IGl0KyspCiAgICAgICAgewogICAgICAgICAgICBidHlwZSB2PSAoKml0KS5maXJzdCxjb3N0ID0gKCppdCkuc2Vjb25kOyAvL2VkZ2UgY29zdAoKICAgICAgICAgICAgaWYoa2V5ICsgY29zdCA8IGtleXNbdl0pIC8vUkVMQVggaWYgcmVsYXhhdGlvbiBjYW4gYmUgZG9uZQogICAgICAgICAgICB7CgogICAgICAgICAgICAgICAgUS5lcmFzZShRLmZpbmQoe2tleXNbdl0sdn0pKTsKICAgICAgICAgICAgICAgIGtleXNbdl0gPSBrZXkgKyBjb3N0OwogICAgICAgICAgICAgICAgUS5pbnNlcnQoe2tleXNbdl0sdn0pOwogICAgICAgICAgICB9CgogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBrZXlzW3RhcmdldF07Cn0KaW50IG1haW4oKQp7CiAgICBpbnQgdDsKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbj4+dDsKICAgIHdoaWxlKHQtLSkKICAgIHsKICAgICAgICBtYXAgPHN0cmluZyxpbnQ+IG5hbWV0b2luZGV4OwogICAgICAgIGJ0eXBlIGksaixuOwogICAgICAgIGJ0eXBlIHUsdix3LG5laWdoYm91cnM7CiAgICAgICAgc3RyaW5nIG5hbWU7CiAgICAgICAgLy9HUkFQSCBJTlBVVAogICAgICAgIGNpbj4+bjsKCiAgICAgICAgdnZwaWkgRyhuKzEsdnBpaSgpKTsgLy8wIC0tPiBuIGNpdGllcwoKICAgICAgICBmb3IodT0xO3U8PW47dSsrKQogICAgICAgIHsKICAgICAgICAgICAgLy9HLnB1c2hfYmFjayh2cGlpKCkpOwogICAgICAgICAgICBjaW4+Pm5hbWU7CiAgICAgICAgICAgIGNpbj4+bmVpZ2hib3VyczsKCiAgICAgICAgICAgIG5hbWV0b2luZGV4W25hbWVdID0gdTsKCiAgICAgICAgICAgIGZvcihqPTE7ajw9bmVpZ2hib3VycztqKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGNpbj4+dj4+dzsKICAgICAgICAgICAgICAgIEdbdV0ucHVzaF9iYWNrKG1ha2VfcGFpcih2LHcpKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAvL0dSQVBIIElOUFVUIENPTVBMRVRFRAogICAgICAgIC8vRElKIElOUFVUCiAgICAgICAgY2luPj5uOy8vbm8gb2YgcXVlcmllcwogICAgICAgIHN0cmluZyBzdGFydCx0YXJnZXQ7CiAgICAgICAgZm9yKGk9MTtpPD1uO2krKykKICAgICAgICB7CiAgICAgICAgICAgIGNpbj4+c3RhcnQ+PnRhcmdldDsKICAgICAgICAgICAgdSA9IG5hbWV0b2luZGV4W3N0YXJ0XTsKICAgICAgICAgICAgdiA9IG5hbWV0b2luZGV4W3RhcmdldF07CiAgICAgICAgICAgIGNvdXQ8PGRpamtzdHJhKEcsdSx2KTw8IlxuIjsKICAgICAgICB9CiAgICB9CgogICAgcmV0dXJuIDA7Cn0K