传送门修建计划

题目描述

2050年，Z国基建能力空前强大，甚至能建设传送门了！传送门可以建设在两个城市之间，人们及汽车（当然也可以携带其他东西）在建设两个点对点的传送门之间可以实现瞬间传送（路上花费的时间为0）。
S省在$n$个城市间原有$m$条高速公路连接，而且任意两个城市之间至多有一条高速公路直接相连。S省G部门计划将所有高速公路使用传送门代替，但是在上报建设规划时，由于传送门成本实在太高了，而且有可能破坏传送门路途中的生态，所以上级G部门规定有$d$对传送门暂停建设，只能使用原有的高速公路连接。S省负责人Z想知道，传送门建设后，现在任意两个城市之间的最短通行时间是多少，作为G部门的编程家X，你能回答Z提出的问题吗？

输入格式

输入文件第一行为一个整数$n$（$2<n≤100$）,表示城市的个数。这些城市编号从$1$到$n$。

第二行为一个整数$m$（$n-1≤m≤\frac{1}{2} n(n-1)$），表示高速公路的数目（能够保证所有城市通过若干高速公路实现连接，而不是孤立的）。

接下来的$m$行，每行$3$个整数$i,j,k$（$1≤i,j≤n,i≠j,0<k≤100$），表示城市$i$与$j$之间通过高速公路的通行时间为$k$。

接下来一行为一个整数$d$（$1≤d≤m$），表示G部门暂停建设传送门的数量。在接下来的$d$行中，每行两个整数$i$和$j$，表示城市$i$与$j$之间禁止修建传送门。

接下来一行为一个整数$o$（$1≤o≤100$），表示Z有多少个问题。在接下来的$o$行中,每行两个整数A和B，分别代表两个城市的编号。

输出格式

输出文件共$o$行，每行一个整数，表示$A$与$B$间最短的通行时间。

样例 #1

样例输入 #1

3
2
1 2 1
2 3 2
1
1 2
1
1 3

样例输出 #1

1

数据规模与约定

对于 $60\%$ 的数据，$o=1$。