Description

N个站，之间连了M条双向的通路！但每条路都规定了一个速度的限制值，在这条路上必须以这个速度前进！所以在 前进的时候要调整速度，现决定尽量使调整的幅度小一些，也就是使走过的路的速度最大值与最小值之差最小！

Format

Input

第一行有2个正整数N , M , 分别表示站点数，路径数.

接下来M行，每行有3个正整数 X, Y, V表示X， Y之间有一条路，其Speed值是V。

再接下来是数K， 表示任务数，

下面K行，每行有一对正整数P，Q ，表示一个任务从P到Q.

(1<=n<=200, 1<=m<=1000, 1<=K<=10)

Output

对于每一个任务输出一行，仅一个数，即最大速度与最小速度之差。

Samples

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

1
0