Description

快放国庆了，GL 很是苦恼呀，因为每次回家坐车路途都要经受一段折磨。  

SC 省有许多城市，城市之间通过一种崎岖的且奇怪的高速公路进行交流，每条高速公路都对行驶在上面的车限制了固定的 Speed，同时 GL 在学校舒服惯了，对行驶的车“舒适度”有

特殊要求，即乘坐过程中最高速度与最低速度的差越小乘坐越舒服 ,(理解为由于高速公路上的限速要求不同，车必须瞬间提速/降速，多让人折磨痛苦呀)

但 GL 对时间却没要求，现在要你找出一条城市间的最舒适的路径。(所有的高速公路都是双向的）。

Input Format

输入包括多个测试实例，每个实例包括：

第一行有 2 个正整数 n (1<n<=200)和 m (m<=1000),表示有 N 个城市和 M 条高速公路。 

接下来的行是三个正整数 StartCity,EndCity,speed,表示从表面上看 StartCity 到 EndCity,限速为 speed。speed<=1000000 

然后是一个正整数 Q（Q<11),表示寻路的个数。 

接下来 Q 行每行有 2 个正整数 Start,End, 表示寻路的起终点。  

Output Format

每个寻路要求输出一行，仅输出一个非负整数表示最佳路线的舒适度最高速与最低速的差。如果起点和终点不能到达，那么输出-1。

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

1
0

Hint

Source

套题 my01