1 /*
 2 Author:    Leo.W
 3 Descriptipn:  城市間的道路通行，尋找從A城到B城，其間經(jīng)過的路線最高速與最低速極差最小的路線，并輸出這個最小值。 
 4 How to Do:    并查集（最小生成樹的Kruskal算法）+ 貪心；
 5               先將道路權值自小到大排序，再依次枚舉權值下限，每次枚舉一個下限時，初始化一次，然后Kruskal算法
 6               直到A、B兩點被連通，記錄這一路的極值。接著循環(huán)枚舉下一個下限，即比前一個下限大一點的權值。直到
 7               所有權值被枚舉完,此時極值中的最小值就得到了。
 8   */
 9 #include <cstdio>
10 #include <iostream>
11 #include <algorithm>
12 #include <string.h> 
13 using namespace std;
14 #define INF 0x7fffffff
15 #define MAXD 205
16 #define MAXN 1005
17 struct line{
18     int bg;
19     int ed;
20     int val;
21 }road[MAXN];
22 int par[MAXD],rank[MAXD];
23 int n,m;
24 
25 int cmp(line a,line b){
26     return a.val<b.val;
27 }
28 int findSet(int x){
29     if(x!=par[x])
30         par[x]=findSet(par[x]);
31     return par[x];
32 }
33 bool Union(int x,int y){
34     x=findSet(x);
35     y=findSet(y);
36     if(x==y)    return false;
37     if(rank[x]>rank[y])
38         par[y]=x;
39     else{
40         if(rank[x]==rank[y])
41             rank[y]++;
42         par[x]=y;
43     }
44     return true;
45 }
46 inline void makeSet(int n){
47     int i;
48     for(i=1;i<=n;i++)//從1到n
49         par[i]=i,rank[i]=0;
50 }
51 int main(){
52     //freopen("in.txt","r",stdin);
53     while (scanf("%d%d",&n,&m)!=EOF){
54         int i,j;
55         for(i=0;i<m;i++)
56             scanf("%d%d%d",&road[i].bg,&road[i].ed,&road[i].val);
57         sort(road,road+m,cmp);//權值自小到大排序
58         int cases;    
59         scanf("%d",&cases);
60         while (cases--){
61             int st,en,Min=INF;
62             scanf("%d%d",&st,&en);
63             for(i=0;i<m;i++){
64                 makeSet(n);
65                 for(j=i;j<m;j++){
66                     if(Union(road[j].bg,road[j].ed))
67                         if(findSet(st)==findSet(en)){
68                             if(Min>road[j].val-road[i].val)
69                                 Min=road[j].val-road[i].val;
70                             break;
71                         }
72                 }
73             }
74             if(Min!=INF)
75                 printf("%d\n",Min);
76             else
77                 printf("-1\n");
78         }
79     }
80     return 0;
81 }
82