1 #include<iostream> 2 #include<algorithm> 3 #include<cmath> 4 #include<cstdio> 5 using namespace std; 6 #define maxn 300 7 #define INF 0x3fffffff 8 int par[maxn]; 9 int n,m;10 11 struct node12 {13     int x;14     int y;15     int w;16 };17 node e[maxn * maxn / 2];18 int cmp(const node& a,const node &b)19 {20     return a.w < b.w;21 }22 void init()23 {24     for(int i = 1; i <= n; i++)25         par[i] = i;26 }27 int Find(int x)28 {29     int t,r,k;30     k = x;31     while(x != par[x])32         x = par[x];33     while(k != x)//tanta34     {35         t = par[k];36         par[k] = x;37         k = t;38     }39     return x;40 }41 void Merge(int x,int y)42 {43     int a = Find(x);44     int b = Find(y);45     if(a != b)46     {47         par[a] = b;48     }49 }50 void kruskal()51 {52     int q,st,en,mindis,i,j;53     while(cin>>n>>m)54     {55         for(int i = 0; i < m; i++)56             cin>>e[i].x>>e[i].y>>e[i].w;57         sort(e,e+m,cmp);58         cin>>q;59         while(q--)60         {61             cin>>st>>en;62             mindis = INF;63             for(i = 0; i < m ; i++)//meijuzuixiao64             {65                 init();66                 for(j = i; j < m; j++)//zhaozuidabian67                 {68                     Merge(e[j].x,e[j].y);69                     if(Find(st) == Find(en))//起点终点相连70                     {71                         mindis = min(mindis,e[j].w - e[i].w);72                         break;73                     }74                 }75                 if(j == m) break; //j == m 继续枚举也不可能找到76             }77             if(mindis != INF) cout<<mindis<<endl;78             else cout<<"-1"<<endl;79         }80     }81 }82 int main()83 {84     freopen("input.txt","r",stdin);85     kruskal();86     return 0;87 }