SP15 SHPATH - The Shortest Path

给定一些城市。每一条直接连接两个城市的交通线都有一个大于零的交通费用。需要找出若干对城市间的最小交通费用。 每条城市间交通路径的费用和最多为 $200000$。每个城市的名称是一个包含小写字母 `a` ~ `z` 的字符串，长度最多为 $10$。

第一行输入一个数 $s$，测试数据的组数。（$s \le 10$） 对于每一组测试数据，第一行输入一个数 $n$，城市的数量。（$n \le 10000$） 之后对于每个 $n$，输入一个字符串 $p$，即城市的名称。 下一行输入一个数 $p$，与这个城市直接相邻的城市的数量。 之后 $p$ 行，每行输入两个数 $nr$ 和 $cost$。$nr$ 为与该城市相邻的城市的编号（编号按输入顺序从 $1$ 开始），$cost$ 为这条路径的交通费用。 接下来输入一个数 $r$，查询组数。（$r \le 100$） 之后 $r$ 行，每行输入两个字符串，起点和终点城市的名称。 每两组测试数据之间用空行隔开。

对于每一个查询，输出一行，两个城市间最小的交通费用。

**Warning: large Input/Output data, be careful with certain languages**