Даден е списък с градове. Всяка пряка връзка между два града има своя транспортна цена. Намерете пътя с минимални транспортни разходи между два града. Максималната сума на транспортните разходи между два града е 200000. Името на града е текстов низ с максимална дължина 10 символа, съдържащ знаците [a ... z].

Вход: 
На първия ред на стандартния вход е зададен броят S на тестовете. На втори ред от стандартния вход е даден броят N на градовете. Следващите N реда съдържат:
- един ред с име на града NAME;
- един ред с броя P на съседните градове;
- един ред с 2 стойности: индекс на свързан град NR и транспортна цена COST;
следващия ред съдържа броя R на пътищата за намиране. Следващите R реда съдържат двойка имена на градове [NAME1 NAME2], отделени с интервал.

Изход: 
Програмата трябва да изведе R на брой редове, съдържащи минималната транспортна цена между градовете NAME1 и NAME2.

Ограничения: 
1 <= S <= 10; 1 <= N <= 10000; 1 <= R <= 100.

Примерен вход:	
1
4
burgas
2
2 1
3 3
varna
3
1 1
3 1
4 4
plovdiv
3
1 3
2 1
4 1
sofia
2
2 4
3 1
2
burgas sofia
varna sofia	

Примерен изход:
3
2