问题描述

小何是一个优秀的赛车手！，小何的赛车训练场地由若干个检查点（节点）和连接它们的赛道（边）组成。每条赛道都有一个固定的速度限制。有一天xsy请求小何同志，让小何同志带他体验一下赛车的乐趣。 作为贴心的小何同志，自然想让xsy的乘坐过程更加舒适，我们规定乘坐过程中最高速度与最低速度的差值越小，舒适度越高（赛车可瞬间提速或降速，无需考虑加速过程）。小何对赛车时间没有要求，你能帮助小何同志找出两城市间最舒适的航线吗？注：作为最优秀的赛车手，小何在赛道上行驶时，自然是按照赛道允许的最高速度来啦

输入格式

第一行包含两个整数 $n$ 和 $m$，表示检查点的数量和赛道的数量。检查点编号从 $1$ 到 $n$。

接下来m行，每行包含三个整数 $u$ , $v$ , $w$，表示检查点u和v之间有一条双向赛道，速度限制为 $w$。

其中， $u (1 ≤ u ≤ n)$, $v (1 ≤ v ≤ n)$, $w (1 ≤ w ≤ 10^6 )$

接下来一行包含一个整数 $q$，表示查询次数。

接下来$q$行，每行包含两个整数 $s$, $t$ ，表示起点为$s$，终点为 $t$。

输出格式

对于每个查询，输出一个整数，表示找到的最小差值。如果无法从终点到达起点，输出 $-1$。

输入样例

4 4
1 2 2
2 3 4
1 4 1
3 4 2
2
1 3
1 2

输出样例

1
0

评测数据规模

对于所有评测数据，$1 ≤ n ≤ 200$，$1 ≤ m ≤ 10^3$，$1 ≤ w ≤ 10^6$，$1 ≤ q ≤ 11$。